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 signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S[2020];
short L[1500][1500],R[1500][1500];
int dp[1500][1500];


void solve() {
	int i,j,k,l,r,x,y,x2,y2; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FORR(c,S[y]) {
			if(c!='#') c-='0';
			else c=0;
		}
	}
	ll ret=0;
	for(y=N-1;y>=0;y--) {
		L[y][N]=N;
		R[y][N]=-1;
		for(x=N-1;x>=0;x--) {
			int down=(y<N-1) && (S[y+1][x]>0);
			int right=(x<N-1) && (S[y][x+1]>0);
			
			if(S[y][x]==0) {
				for(y2=y;y2<N;y2++) {
					L[y][x]=N;
					R[y][x]=-1;
				}
			}
			else {
				dp[y][x]=dp[y+1][x]+dp[y][x+1];
				L[y][x]=x;
				if(down&&right) {
					R[y][x]=R[y][x+1];
					
					int r=0;
					for(y2=y+1;y2<N;y2++) {
						if(L[y2][x+1]<=R[y2][x] && r<L[y2][x+1]) {
							dp[y][x]-=dp[y2][L[y2][x+1]];
						}
						r=R[y2][x];
						R[y2][x]=max(R[y2][x],R[y2][x+1]);
						L[y2][x]=min(L[y2][x],L[y2][x+1]);
					}
				}
				else if(down) {
					R[y][x]=x;
				}
				else if(right) {
					R[y][x]=R[y][x+1];
					for(y2=y+1;y2<N;y2++) {
						L[y2][x]=L[y2][x+1];
						R[y2][x]=R[y2][x+1];
					}
				}
				else {
					R[y][x]=x;
					for(y2=y+1;y2<N;y2++) {
						L[y2][x]=N;
						R[y2][x]=0;
					}
				}
				ret+=S[y][x]*dp[y][x];
				dp[y][x]+=S[y][x];
			}
		}
	}
	
	
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}