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;
namespace io{
    const int l=1<<20;
    char buf[l],*s,*t,c;
    inline void gc(){
        if(s==t){
            t=(s=buf)+fread(buf,1,l,stdin);
            c=s==t?EOF:*s++;
        }else c=*s++;
    }
    template<class IT>inline void gi(IT &x){
        x=0;gc();while(c<'0'||c>'9')gc();
        while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}
    }
    char buf0[20];int a;
    template<class IT>inline void pi(IT x){
        if(x<0){putchar('-');x=-x;}
        do buf0[++a]=x%10+48;while(x/=10);
        while(a)putchar(buf0[a--]);
        putchar('\n');
    }
};
using io::gi;
using io::pi;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll > pil;
typedef pair<ll ,int> pli;
typedef pair<ll ,ll > pll;
typedef vector<int> vi;
typedef vector<ll > vl;
#define pque priority_queue
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const int N=505;
int a[N][N],f[N][N];
short l[N][N],r[N][N];
char c[N];
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,i,j,k,t;short m;ll ans=0ll;
    scanf("%d",&n);
    rep(i,1,n){
		scanf("%s",c+1);
		rep(j,1,n)a[i][j]=((c[j]=='#')?0:(c[j]^48));
	}
	per(i,n,1)per(j,n,1){
		if(a[i][j]){
			if(a[i+1][j]){
				if(a[i][j+1]){
					l[j][i]=j;r[j][i]=r[j+1][i];
					t=f[i][j+1]+f[i+1][j];m=0;
					rep(k,i+1,n){
						if(r[j][k]>=l[j+1][k]&&l[j+1][k]>m)t-=f[k][l[j+1][k]];
						cmax(m,r[j][k]);
						cmin(l[j][k],l[j+1][k]);
						cmax(r[j][k],r[j+1][k]);
					}
					f[i][j]=t;
				}else{
					l[j][i]=r[j][i]=j;
					f[i][j]=f[i+1][j];
				}
			}else{
				if(a[i][j+1]){
					memcpy(l[j]+i,l[j+1]+i,(n-i+1)<<1);
					memcpy(r[j]+i,r[j+1]+i,(n-i+1)<<1);
					l[j][i]=j;
					f[i][j]=f[i][j+1];
				}else l[j][i]=r[j][i]=j;
			}
			ans+=a[i][j]*f[i][j];
			f[i][j]+=a[i][j];
		}else{
			memset(l[j]+i,0x3f,(n-i+1)<<1);
			memset(r[j]+i,0   ,(n-i+1)<<1);
		}
		//printf("(%d,%d) f=%d\n",i,j,f[i][j]);
		//rep(k,i,n)printf("(%d,[%d,%d])\n",k,l[j][k],r[j][k]);
	}
	printf("%lld",ans);
    return 0;
}