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 mp make_pair
#define fi first
#define se second
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
#define eef(i,x)for(int i=head[x],y=e[i].to;y;i=e[i].next,y=e[i].to)
int read(){char c=getchar();int d=0,f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());return d*f;}
char Read(){char c=getchar();while(c<'0'||c>'9')c=getchar();return c;}
int getdigit(char c){return (c<'0'||c>'9')?-1e9:(c-'0');}
typedef pair<int,int>PII;
typedef long long LL;
const double pi=acos(-1);
const int N=1510,mod=1e9+7;
int n,c1[N][N],c2[N][N];LL ans,dp[N][N];
char a[N][N];
int main(){
	n=read();
	ref(i,1,n)scanf("%s",a[i]+1);
	ref(i,1,n){
		if(i==1){
			ref(j,1,n)dp[i][j]=max(0LL,dp[i][j-1]+getdigit(a[i][j]));
			ref(j,1,n)c1[j][1]=j;
			continue;
		}
		ref(j,1,n){
			bool w1=getdigit(a[i][j-1])>=0,w2=getdigit(a[i-1][j])>=0;
			bool W1=getdigit(a[i-1][j-1])>=0,W2=getdigit(a[i-2][j])>=0;
			ref(k,1,i){
				int C1=0;
				if(k==i)C1=j;else{
					if(w1)C1=c1[j-1][k];
					if(w2)C1=max(C1,c1[j][k]);
				}
				c1[j][k]=C1;
			}
			ref(k,1,i-1){
				int C2=1e9;
				if(k==i-1)C2=j;
				if(W1)C2=c2[j-1][k];
				if(W2&&k!=i-1)C2=min(C2,c2[j][k]);
				c2[j][k]=C2;
			}
		}
		ref(j,1,n)if(getdigit(a[i][j])>=0){
			int v=getdigit(a[i][j]);
			bool w1=getdigit(a[i][j-1])>=0,w2=getdigit(a[i-1][j])>=0;
			if(j==1){
				dp[i][j]=dp[i-1][j];
			}else if(j>1){
				if(!w1&&!w2)dp[i][j]=0;else
				if( w1&&!w2)dp[i][j]=dp[i][j-1];else
				if(!w1&& w2)dp[i][j]=dp[i-1][j];else
				if( w1&& w2){
					LL s=dp[i-1][j]+dp[i][j-1],la=1e9;
					def(k,i-1,1){
						if(c1[j-1][k]>=c2[j][k]&&la>c1[j-1][k])
							s-=dp[k][c1[j-1][k]];
						la=c2[j][k];
					}
					dp[i][j]=s;
				}
			}
			dp[i][j]+=v;
		}
	}
	ref(i,1,n)ref(j,1,n){
		int v=getdigit(a[i][j]);
		if(v>=0)ans+=(dp[i][j]-v)*v;
	}
	printf("%lld\n",ans);
}