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:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<int>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define mem(a) memset((a),0,sizeof(a))
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
const int N=1504,inf=1e9;
int wx[N>>1][N],wu[N>>1][N],WX[N],WU[N],lef[N>>1][N],rig[N>>1][N],mn[N][N],mx[N>>1][N],q[N];
int s1[N>>1],sum,s2[N>>1][N],s3[N>>1][N],s4[N][N],F[N>>1][N],G[N>>1][N],s[N][N],mtp[N][N],only[N];
char a[N][N];
ll ans;
int brh(int a,int b,int l){
	if(mtp[a][b]>l)return 0;
	l=min(l,min(WX[a],WX[b])); if(l<0)return 0; //cout<<a<<" "<<b<<" fjzzq " <<l<<endl;
	assert(l);
	return s1[l]-s2[l][a+1]-s3[l][b-1]+s4[a+1][b-1];
}
void add(int a,int b){
	only[a]+=b; sum+=b;
}
void Solve(int A,int B,int C){//注意数组清空 
	//{cout<<A<<" "<<B<<" "<<C<<endl;For(i,1,A){For(j,1,C)wri(F[i][j]); puts("");}For(i,1,B){For(j,1,C)wri(G[i][j]); puts("");}}
	//mem(wx); mem(wu); mem(lef); mem(rig); mem(mn); mem(mx); mem(q); mem(s1); mem(s2);
	//if(A==23&&B==22&&C==23)cout<<ans<<endl;
	Rep(i,B,1)Rep(j,C,1)if(G[i][j]){
		wx[i][j]=i;
		if(i<B)wx[i][j]=max(wx[i][j],wx[i+1][j]);
		if(j<C)wx[i][j]=max(wx[i][j],wx[i][j+1]);
	}else wx[i][j]=-inf;
	For(i,1,A)For(j,1,C)if(F[i][j]){
		wu[i][j]=i;
		if(i>1)wu[i][j]=min(wu[i-1][j],wu[i][j]);
		if(j>1)wu[i][j]=min(wu[i][j-1],wu[i][j]);
	}else wu[i][j]=inf;
	For(i,1,C){WX[i]=wx[1][i]; WU[i]=wu[A][i];}
	//For(i,1,C)wri(WX[i]); puts("");
	For(i,1,B)For(j,1,C)if(G[i][j]){
		lef[i][j]=i==1?j:inf;
		rig[i][j]=i==1?j:-inf;
		if(i>1){
			lef[i][j]=min(lef[i][j],lef[i-1][j]);
			rig[i][j]=max(rig[i][j],rig[i-1][j]);
		}
		if(j>1){
			lef[i][j]=min(lef[i][j],lef[i][j-1]);
			rig[i][j]=max(rig[i][j],rig[i][j-1]);
		}
	}else {lef[i][j]=inf; rig[i][j]=-inf;}
	For(i,1,C)For(j,1,C)mn[i][j]=inf;
	For(i,1,B)For(j,1,C)if(lef[i][j]<=rig[i][j])mn[lef[i][j]][rig[i][j]]=min(mn[lef[i][j]][rig[i][j]],i);
	For(i,1,C)Rep(j,C,i){
		if(i>1)mn[i][j]=min(mn[i-1][j],mn[i][j]);
		if(j<C)mn[i][j]=min(mn[i][j+1],mn[i][j]);
	}
	For(i,1,C){
		mtp[i][i]=1;
		For(j,i+1,C)mtp[i][j]=mn[i][j]>min(WX[i],WX[j])?inf:mn[i][j];
	}
	Rep(i,A,1)Rep(j,C,1)if(F[i][j]){
		mn[i][j]=i==A&&G[1][j]?j:inf;
		mx[i][j]=i==A&&G[1][j]?j:-inf;
		if(i<A){
			mn[i][j]=min(mn[i+1][j],mn[i][j]);
			mx[i][j]=max(mx[i+1][j],mx[i][j]);
		}
		if(j<C){
			mn[i][j]=min(mn[i][j+1],mn[i][j]);
			mx[i][j]=max(mx[i][j+1],mx[i][j]);
		}
	}else {mn[i][j]=inf; mx[i][j]=-inf;}
	For(i,1,B)For(j,1,C)if(lef[i][j]<=rig[i][j]){
		s1[i]+=G[i][j];
		s2[i][lef[i][j]]+=G[i][j];
		s3[i][rig[i][j]]+=G[i][j];
		s4[lef[i][j]][rig[i][j]]+=G[i][j];
	}
	For(i,1,B){
		s1[i]+=s1[i-1];
		For(j,1,C)s3[i][j]+=s3[i-1][j]+s3[i][j-1]-s3[i-1][j-1];
		Rep(j,C,1)s2[i][j]+=s2[i-1][j]+s2[i][j+1]-s2[i-1][j+1];
	}
	Rep(i,C,1)For(j,i,C){
		s4[i][j]+=s4[i+1][j]+s4[i][j-1]-s4[i+1][j-1];
	}
	//cout<<brh(4,8,11)<<" "<<mtp[4][8]<<" "<<WX[4]<<" "<<WX[8]<<endl;
	For(i,1,A){
		int l=1,r=0; sum=0; 
		int L=1,R=0;
		For(j,1,C)if(mn[i][j]<=mx[i][j]){
			assert(L<=mn[i][j]&&R<=mx[i][j]);
			For(k,R+1,mx[i][j])if(WU[k]<=i&&G[1][k]){
				int o=r;
				while(l<=r&&q[l]<L)l++;
				while(l<=o&&WX[q[o]]<=WX[k])o--;
				if(l<=r)add(q[r],-brh(q[r],k,WX[q[r]]));
				For(i,max(o,l),r-1)add(q[i],brh(q[i],k,WX[q[i+1]])-brh(q[i],k,WX[q[i]]));
				//cout<<i<<" "<<j<<" "<<sum<<" "<<mn[i][j]<<" "<<mx[i][j]<<" "<<brh(k,k,B)<<endl;
				//cout<<k<<" "<<sum<<" "<<only[1]<<" "<<only[k]<<" "<<WU[1]<<endl;
				q[r=o+1]=k; only[k]=brh(k,k,B); sum+=only[k];
			}
			//cout<<sum<<" "<<mn[i][j]<<" "<<mx[i][j]<<" "<<i<<" "<<j<<" "<<" "<<endl;
			For(k,L,mn[i][j]-1)if(WU[k]<=i&&G[1][k])sum-=only[k];
			L=mn[i][j]; R=mx[i][j];
			ans+=sum*F[i][j];
			//if(i>10)cout<<i<<" "<<j<<" "<<sum<<" "<<mn[i][j]<<" "<<mx[i][j]<<" "<<only[6]<<" "<<brh(6,6,3)<<endl;
		}
	}
	For(i,1,B){s1[i]=0; For(j,1,C)s2[i][j]=s3[i][j]=0;} 
	For(i,1,C)For(j,i,C)s4[i][j]=0;//exit(0);
	//if(A==23&&B==22&&C==23)cout<<ans<<endl;
	//if(ans){cout<<ans<<endl; exit(0);}
}
void solve(int l,int r,int u,int d){
	if(l==r&&u==d)return;
	if(r-l>=d-u){
		int mid=(l+r)>>1;
		For(i,l,mid)For(j,u,d)F[i-l+1][j-u+1]=s[i][j];
		For(i,mid+1,r)For(j,u,d)G[i-mid][j-u+1]=s[i][j];
		Solve(mid-l+1,r-mid,d-u+1);  //cout<<ans<<" "<<mid-l+1<<" "<<r-mid<<" "<<d-u+1<<endl;
		solve(l,mid,u,d); solve(mid+1,r,u,d);
	}else{
		int mid=(u+d)>>1;
		For(i,u,mid)For(j,l,r)F[i-u+1][j-l+1]=s[j][i];
		For(i,mid+1,d)For(j,l,r)G[i-mid][j-l+1]=s[j][i];
		Solve(mid-u+1,d-mid,r-l+1); //cout<<ans<<" "<<mid-u+1<<" "<<d-mid<<" "<<r-l+1<<endl;
		solve(l,r,u,mid); solve(l,r,mid+1,d);
	}
}
int main(){
	int n=read();
	For(i,1,n){
		scanf("%s",a[i]+1);
		For(j,1,n)s[i][j]=a[i][j]=='#'?0:a[i][j]-'0';
	}
	solve(1,n,1,n);
	cout<<ans<<endl;
}
/*
6
111111
##11#1
1##1#1
11##11
111111
1#11#1
*/