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 re 
int v[2][1510][1510],lt[1510][1510],rt[1510][1510],bt[1510],ut[1510];
int ln[1510][1510],rn[1510][1510],nn[1510][1510],lc[1510],mn[1510][1510];
char ss[1510];
long long ans;
int num(re int x1,re int x2,re int l)
{
	l=std::min(bt[x1],std::min(bt[x2],l));
	if(l<mn[x1][x2])return 0;
	return lc[l]-ln[l][x2-1]-rn[l][x1+1]+nn[x1+1][x2-1];
}
void dp(re int vc,re int x1,re int y1,re int x2,re int y2)
{
	for(re int i=x1-1;i<=x2+1;i++)
		for(re int j=y1-1;j<=y2+1;j++)lt[i][j]=1<<30,rt[i][j]=-1<<30,ln[i][j]=rn[i][j]=0;
	for(re int i=y1-1;i<=y2+1;i++)
		for(re int j=y1-1;j<=y2+1;j++)nn[i][j]=0,mn[i][j]=1<<30;
	for(re int i=y1-1;i<=y2+1;i++)bt[i]=-1<<30;
	for(re int i=x1;i<=x2;i++)
	{
		for(re int j=y1;j<=y2;j++)
		if(v[vc][i][j]){
			if(i==x1)lt[i][j]=rt[i][j]=j;
			lt[i][j]=std::min(lt[i][j],std::min(lt[i-1][j],lt[i][j-1]));
			rt[i][j]=std::max(rt[i][j],std::max(rt[i-1][j],rt[i][j-1]));
			re int x=lt[i][j],y=rt[i][j];
			if(x<=y)
			{
				mn[x][y]=std::min(mn[x][y],i),nn[x][y]+=v[vc][i][j];
				ln[i][y]+=v[vc][i][j],rn[i][x]+=v[vc][i][j];
			}//printf("**lr**%d %d %d %d %d\n",i,j,x,y,mn[x][y]);
		}
	}
	for(re int i=x1;i<=x2;lc[i]=ln[i][y2],i++)
		for(re int j=y1;j<=y2;j++)
			ln[i][j]+=ln[i-1][j]+ln[i][j-1]-ln[i-1][j-1];
	for(re int i=x1;i<=x2;i++)
		for(re int j=y2;j>=y1;j--)
			rn[i][j]+=rn[i-1][j]+rn[i][j+1]-rn[i-1][j+1];
	for(re int i=y1;i<=y2;i++)
		for(re int j=y2;j>=y1;j--)
			mn[i][j]=std::min(mn[i][j],std::min(mn[i-1][j],mn[i][j+1]));
	for(re int i=y2;i>=y1;i--)
		for(re int j=y1;j<=y2;j++)
			nn[i][j]+=nn[i+1][j]+nn[i][j-1]-nn[i+1][j-1];
	for(re int i=x2;i>=x1;i--)
		for(re int j=y2;j>=y1;j--)
		if(v[vc][i][j]){
			bt[j]=std::max(bt[j],std::max(i,bt[j+1]));//printf("*k*%d %d %d\n",i,j,bt[j]);
		}else bt[j]=-1<<30;
	//for(re int i=y1;i<=y1;i++)if(bt[i]!=-1<<30)printf("**b**%d %d %d %d %d %d:%d %d %d %d\n",vc,i,bt[i],mn[i][i],ln[bt[i]][i],num(i,i,bt[i]),x1,y1,x2,y2);
}
int ov[1510],q[1510];
void clac(re int vc,re int x1,re int y1,re int x2,re int y2)
{//puts("*************");
	for(re int i=x1-1;i<=x2+1;i++)
		for(re int j=y1-1;j<=y2+1;j++)lt[i][j]=1<<30,rt[i][j]=-1<<30;
	for(re int i=y1-1;i<=y2+1;i++)ut[i]=1<<30;
	for(re int i=x2;i>=x1;i--)
	{
		for(re int j=y2;j>=y1;j--)
		if(v[vc][i][j]){
			if(i==x2)lt[i][j]=rt[i][j]=j;
			lt[i][j]=std::min(lt[i][j],std::min(lt[i+1][j],lt[i][j+1]));
			rt[i][j]=std::max(rt[i][j],std::max(rt[i+1][j],rt[i][j+1]));
		}
	}
	for(re int i=x1;i<=x2;i++)
		for(re int j=y1;j<=y2;j++)
		if(v[vc][i][j]){
			ut[j]=std::min(ut[j],std::min(i,ut[j-1]));
		}else ut[j]=1<<30;
	//printf("*ut*%d %d %d\n",i,x1,ut[3]);}
	re int ii=0,jj=0,jj1=0;
	for(re int i=x1;i<x2;i++)
	{
		re long long ncm=0,ta=0;jj=y1-1;jj1=y1-1;
		for(re int j=y1;j<=y2;j++)ov[j]=0;
		for(re int j=y1;j<=y2;j++)
		if(lt[i][j]<=rt[i][j]){
			while(jj<rt[i][j])
			{//printf("**%d %d %d %d %d %d %d %d %d %d %d\n",vc,x1,y1,x2,y2,jj+1,ut[jj+1],bt[jj+1],lt[i][j],rt[i][j]);
				
				if(ut[++jj]>i)continue;//printf("*****************ujj**%d %d\n",jj,ut[jj]);
				ov[jj]=num(jj,jj,bt[jj]);
				ncm+=ov[jj];q[ta+1]=0;bt[0]=-1<<30;
				for(;q[ta]>jj1;ta--)
				{
					re int tt=num(q[ta],jj,bt[q[ta]])-num(q[ta],jj,bt[q[ta+1]]);
					//printf("**jj**%d %d %d %d %d\n",i,j,jj,q[ta],tt);
					ov[q[ta]]-=tt;ncm-=tt;
					if(bt[q[ta]]>bt[jj])break;
				}q[++ta]=jj;
			}
			while(jj1<lt[i][j]-1)
			{
				ncm-=ov[++jj1];
			}//printf("*ll*%d %d %d %d %lld\n",jj,jj1,ut[jj],num(jj,jj,bt[jj]),ncm);
			ans+=v[vc][i][j]*ncm;
		}
	}
}
void dc(re int vc,re int x1,re int y1,re int x2,re int y2)
{
	if(x2==x1&&y2==y1)return;
	if(x2-x1<y2-y1)vc^=1,std::swap(x1,y1),std::swap(x2,y2);
	re int xx=(x1+x2)/2;
	dc(vc,x1,y1,xx,y2);
	dc(vc,xx+1,y1,x2,y2);
	dp(vc,xx+1,y1,x2,y2);
	clac(vc,x1,y1,xx+1,y2);
	//if(vc)printf("***%d %d %d %d %d %lld\n",vc,y1,x1,y2,x2,ans);
	//else printf("***%d %d %d %d %d %lld\n",vc,x1,y1,x2,y2,ans);
}
int main()
{
	re int n;
	scanf("%d",&n);
	for(re int i=1;i<=n;i++)
	{
		scanf("%s",ss+1);
		for(re int j=1;j<=n;j++)v[0][i][j]=v[1][j][i]=(ss[j]=='#'?0:ss[j]-'0');
	}
	dc(0,1,1,n,n);
	printf("%lld\n",ans);
}