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:
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int N=1505;
int S[N],n,u[N][N],l[2][N],r[2][N],flag[N][N];
char A[N][N];
int main(){
	scanf("%d",&n);
	for (register int i=1;i<=n;++i)scanf("%s",A[i]+1);
	for (register int i=1;i<=n;++i)
		for (register int j=1;j<=n;++j)flag[i][j]=A[i][j]>='0'&&A[i][j]<='9';
	for (register int i=0;i<=n;++i)
		for (register int j=0;j<=n;++j)u[i][j]=flag[i][j]?min(i,min(u[i-1][j],u[i][j-1])):1<<30;
	long long ans=0;
	for (register int x=1;x<=n;++x){
		int t=x&1;
		for (register int j=1;j<=n;++j)S[j]=S[j-1]+(u[x][j]<=x?A[x][j]-'0':0);
		for (register int j=n+1;j;--j){
			if (flag[x][j]){
				l[t][j]=j;
				r[t][j]=max(r[t][j+1],j);
				if (l[t][j]<=r[t][j])ans+=(A[x][j]-'0')*(S[r[t][j]]-S[l[t][j]-1]-A[x][j]+'0');
			}
			else l[t][j]=1e9,r[t][j]=-1;
		}
		for (register int i=x-1;i;--i){
			int t=i&1;
			for (register int j=1;j<=n;++j)S[j]=S[j-1]+(u[x][j]<=i?A[x][j]-'0':0);
			for (register int j=n+1;j;--j){
				if (flag[i][j]){
					l[t][j]=min(l[t][j+1],l[t^1][j]);
					r[t][j]=max(r[t][j+1],r[t^1][j]);
					if (l[t][j]<=r[t][j])ans+=(A[i][j]-'0')*(S[r[t][j]]-S[l[t][j]-1]);
				}
				else l[t][j]=1e9,r[t][j]=-1;
			}
		}
	}
	printf("%lld\n",ans);
}