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;
#define ri register int
const int N=505;
int a[N][N],f[N][N],l[N][N],r[N][N];
char s[N];
/* 
f[i][j] (i,j) 能走到的位置的权值和
l[i][j][k]/r[i][j][k] 表示 (i,j) 可以到达的第 k 行最左/右的位置 ，第一维省略
不能走到的点贡献相当于已经清零，因为 (i+1,j) (i,j+1) 共同能走到的点的递增序列里面不会出现这些位置，
且没有被计算到其左上的点的贡献中去 
*/
int main(){
//	freopen("cell.in","r",stdin);
//	freopen("cell.out","w",stdout);
	ri n,i,j,k,now;
	register long long ans;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%s",s+1);
		for(j=1;j<=n;++j)
			a[i][j]=s[j]=='#'?0:s[j]-'0';
	}
	ans=0;
	for(i=n;i;--i)
		for(j=n;j;--j){
			if(a[i][j]==0){
				memset(l[j]+i,127,sizeof(int)*(n-i+1));
				memset(r[j]+i,128,sizeof(int)*(n-i+1));
				continue;
			}
			if(a[i+1][j]==0&&a[i][j+1]==0)
				l[j][i]=r[j][i]=j;
			else if(a[i+1][j]==0)
				memcpy(l[j]+i,l[j+1]+i,sizeof(int)*(n-i+1)),
				memcpy(r[j]+i,r[j+1]+i,sizeof(int)*(n-i+1)),
				l[j][i]=j,
				f[i][j]=f[i][j+1];
			else if(a[i][j+1]==0)
				l[j][i]=r[j][i]=j,
				f[i][j]=f[i+1][j];
			else{
				f[i][j]=f[i][j+1]+f[i+1][j];
				l[j][i]=j;r[j][i]=r[j+1][i];
				now=0;
				for(k=i+1;k<=n;++k){
					if(r[j][k]>=l[j+1][k]&&l[j+1][k]>now)
					//	printf("sub %d %d %d %d\n",i,j,k,l[j+1][k]),
						f[i][j]-=f[k][l[j+1][k]];
					now=max(now,r[j][k]);
					l[j][k]=min(l[j][k],l[j+1][k]);
					r[j][k]=max(r[j][k],r[j+1][k]);
				}
			}
			ans+=a[i][j]*f[i][j];
		//	printf("f %d %d %d\n",i,j,f[i][j]);
			f[i][j]+=a[i][j];
		//	printf("check (%d,%d)\n",i,j);
		//	for(k=i;k<=n;++k)
		//		printf("%d %d %d\n",k,l[j][k],r[j][k]);
		}
	printf("%lld\n",ans);
	return 0;
}