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>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int MAXN=1505;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-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);return x*ny;
}
int Sumv[MAXN][MAXN],rpos[MAXN][MAXN],Mn[2][MAXN][MAXN],Mx[2][MAXN][MAXN],n;ll ans;
char S[MAXN][MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();
	Rep(i,1,n)scanf("%s",S[i]+1);
	for(int i=n,cur=1;i>=1;i--,cur^=1)Red(j,n,1)if(S[i][j]!='#'){
		Sumv[i][j]=Sumv[i+1][j]+Sumv[i][j+1]+(S[i][j]^48),rpos[i][j]=max(max(rpos[i+1][j],rpos[i][j+1]),i);
		Mn[cur][j][i]=j;
		Rep(k,i+1,rpos[i+1][j])Mn[cur][j][k]=Mn[cur^1][j][k];
		Rep(k,max(rpos[i+1][j],i)+1,rpos[i][j+1])Mn[cur][j][k]=Mn[cur][j+1][k];
		Mx[cur][j][i]=j;
		Rep(k,i,rpos[i][j+1])Mx[cur][j][k]=Mx[cur][j+1][k];
		Rep(k,max(rpos[i][j+1],i)+1,rpos[i+1][j])Mx[cur][j][k]=Mx[cur^1][j][k];
		for(int d=i+1,r=min(rpos[i][j+1],rpos[i+1][j]);d<=r;d++){
			if(Mx[cur^1][j][d]>=Mn[cur][j+1][d])
				Sumv[i][j]-=Sumv[d][Mn[cur][j+1][d]],d=rpos[d][Mn[cur][j+1][d]];
		}ans=(ans+1ll*(Sumv[i][j]-(S[i][j]^48))*(S[i][j]^48));
	}cout<<ans<<"\n";
	return 0;
}