Problem: Problem F and F2 are the same problem, but with different constraints and time limits.

We have a board divided into N horizontal rows and N vertical columns of square cells. The cell at the i-th row from the top and the j-th column from the left is called Cell (i,j). Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If A_{i,j}= `1`, `2`, ..., or `9`, Cell (i,j) is empty and the digit A_{i,j} is written on it. If A_{i,j}= `#`, Cell (i,j) is occupied by an obstacle.

Cell Y is reachable from cell X when the following conditions are all met:

* Cells X and Y are different.
* Cells X and Y are both empty.
* One can reach from Cell X to Cell Y by repeatedly moving right or down to an adjacent empty cell.



Consider all pairs of cells (X,Y) such that cell Y is reachable from cell X. Find the sum of the products of the digits written on cell X and cell Y for all of those pairs.

Constraints

* 1 \leq N \leq 500
* A_{i,j} is one of the following characters: `1`, `2`, ... `9` and `#`.

Input

Input is given from Standard Input in the following format:


N
A_{1,1}A_{1,2}...A_{1,N}
A_{2,1}A_{2,2}...A_{2,N}
:
A_{N,1}A_{N,2}...A_{N,N}


Output

Print the sum of the products of the digits written on cell X and cell Y for all pairs (X,Y) such that cell Y is reachable from cell X.

Examples

Input

2
11
11


Output

5


Input

4
1111
11#1
1#11
1111


Output

47


Input

10
76##63##3#
8445669721
75#9542133
3#285##445
749632##89
2458##9515
5952578#77
1#3#44196#
4355#99#1#
298#63587


Output

36065


Input

10
4177143673
7#########
5#1716155#
6#4#####5#
2#3#597#6#
6#9#8#3#5#
5#2#899#9#
1#6#####6#
6#5359657#
5#########


Output

6525

Solution (in CPP):

Solution:
#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
    in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
    in int read()
    {
        int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;
        x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;
    }
    in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
    in int gs(char *s) {char c,*t=s;while(c=gc(),c<=32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
    in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
    in void flush() {if(C>1<<22) ot();}
    template <typename T>
    in void write(T x,char t)
    {
        int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
        if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
    }
    in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=1.5e3+5;
int n,s[N][N],p[N][N],mn[2][N][N],mx[2][N][N];ll ans;
char ch[N][N];
int main()
{
	n=read();for(int i=1;i<=n;i++) gs(ch[i]+1);
	for(int i=n,t=1;i;t^=1,i--) for(int j=n;j;j--) if(ch[i][j]^'#')
	{
		s[i][j]=s[i][j+1]+s[i+1][j]+ch[i][j]-'0';
		p[i][j]=max(max(p[i][j+1],p[i+1][j]),i);
		mn[t][j][i]=j;
		for(int k=i+1;k<=p[i+1][j];k++) mn[t][j][k]=mn[t^1][j][k];
		for(int k=max(p[i+1][j],i)+1;k<=p[i][j+1];k++) mn[t][j][k]=mn[t][j+1][k];
		mx[t][j][i]=j;
		for(int k=i;k<=p[i][j+1];k++) mx[t][j][k]=mx[t][j+1][k];
		for(int k=max(p[i][j+1],i)+1;k<=p[i+1][j];k++) mx[t][j][k]=mx[t^1][j][k];
		int l=i+1,r=min(p[i][j+1],p[i+1][j]);
		while(l<=r)
		{
			if(mx[t^1][j][l]>=mn[t][j+1][l]) s[i][j]-=s[l][mn[t][j+1][l]],l=p[l][mn[t][j+1][l]];
			l++;
		}
		ans+=1ll*(ch[i][j]-'0')*(s[i][j]-(ch[i][j]-'0'));
	}
	write(ans,'\n');
	return ot(),0;
}
//Author: disangan233