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;
const int N=1505,p=1000000007;
int read(){
	int f=1,g=0;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,f[N][N],d[N][N];
typedef unsigned short us;
us a[N][N],l[N][N],r[N][N];
ll ans;
char ch[N];
inline void chkmin(us &x,us y){if (x>y) x=y;}
inline void chkmax(us &x,us y){if (x<y) x=y;}
int main(){
	n=read();
	for (int i=1;i<=n;i++){
		scanf(" %s",ch+1);
		for (int j=1;j<=n;j++)
		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0');
	}
	memset(l,0x3f,sizeof(l));
	for (int i=n;i;i--)
	for (int j=n;j;j--)
	if (a[i][j]){
		int t=f[i+1][j]+f[i][j+1];
		d[i][j]=max(max(d[i][j+1],d[i+1][j]),i);
		if (!a[i][j+1]){l[j][i]=r[j][i]=j;}
		else if (!a[i+1][j]){
			memcpy(l[j]+i,l[j+1]+i,(n-i+1)*2);
			memcpy(r[j]+i,r[j+1]+i,(n-i+1)*2);
			l[j][i]=j;
		}
		else{
			l[j][i]=j;r[j][i]=r[j+1][i];
			us las=0;
			for (int x=i+1;x<=d[i][j];x++){
				if ((l[j+1][x]<=r[j][x])&&(las<l[j+1][x])) t-=f[x][l[j+1][x]];
				chkmax(las,r[j][x]);
				chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);
			}
		}
		ans+=a[i][j]*t;
		f[i][j]=a[i][j]+t;
	}
	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}
	printf("%lld\n",ans);
	return 0;
}