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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <cassert>
#define SIZE 1505

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct BIT
{
	int bit[SIZE];
	int sz;
	
	void init(int S)
	{
		sz=S;
		for(int i=0;i<sz;i++) bit[i]=0;
	}
	void add(int k,int x)
	{
		k++;
		while(k<sz)
		{
			bit[k]+=x;
			k+=k&-k;
		}
	}
	int get(int k)
	{
		k++;
		int ret=0;
		while(k>0)
		{
			ret+=bit[k];
			k-=k&-k;
		}
		return ret;
	}
	int get(int s,int t)
	{
		return get(t)-get(s-1);
	}
};
BIT bit[SIZE];
char str[SIZE];
bool use[SIZE][SIZE];
int rt[SIZE][SIZE];
int l1[SIZE][SIZE],r1[SIZE][SIZE];
int l2[SIZE][SIZE],r2[SIZE][SIZE];
int nxt[SIZE][SIZE],back[SIZE][SIZE];
int ds[SIZE][SIZE],dt[SIZE][SIZE];
int last[SIZE];
int sd[SIZE];
bool active[SIZE];
ll ans;

int get(int y,int s,int t)
{
	return rt[y][t]-(s==0?0:rt[y][s-1]);
}
void solve(vector <string> mp)
{
	if(mp.size()==1)
	{
		int sum=0;
		for(int i=0;i<mp[0].size();i++)
		{
			if(mp[0][i]=='#') sum=0;
			else
			{
				ans+=sum*(mp[0][i]-'0');
				sum+=(mp[0][i]-'0');
			}
		}
		return;
	}
	if(mp.size()<mp[0].size())
	{
		vector <string> nw;
		for(int i=0;i<mp[0].size();i++)
		{
			string S="";
			for(int j=0;j<mp.size();j++) S+=mp[j][i];
			nw.push_back(S);
		}
		//printf("%d\n",nw.size());
		//for(int i=0;i<nw.size();i++) printf("%s\n",nw[i].c_str());
		//return;
		solve(nw);
		return;
	}
	int h=mp.size(),w=mp[0].size();
	/*
	puts("");
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++) printf("%c",mp[i][j]);
		puts("");
	}*/
	ll AA=ans;
	int m1=h/2-1,m2=m1+1;
	for(int i=m1;i>=0;i--)
	{
		for(int j=w-1;j>=0;j--)
		{
			if(mp[i][j]=='#') use[i][j]=false;
			else
			{
				if(i==m1) use[i][j]=true;
				else if(j+1<w&&use[i][j+1]) use[i][j]=true;
				else if(use[i+1][j]) use[i][j]=true;
				else use[i][j]=false;
			}
		}
	}
	for(int i=m2;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(mp[i][j]=='#') use[i][j]=false;
			else
			{
				if(i==m2) use[i][j]=true;
				else if(j-1>=0&&use[i][j-1]) use[i][j]=true;
				else if(use[i-1][j]) use[i][j]=true;
				else use[i][j]=false;
			}
		}
	}
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			rt[i][j]=use[i][j]?mp[i][j]-'0':0;
			if(j>0) rt[i][j]+=rt[i][j-1];
		}
	}
	for(int i=m1;i>=0;i--)
	{
		if(i==m1)
		{
			int now=-1;
			for(int j=0;j<w;j++)
			{
				if(mp[i][j]=='#')
				{
					l1[j][i]=r1[j][i]=-1;
					now=-1;
				}
				else
				{
					if(now==-1) now=j;
					l1[j][i]=now;
					r1[j][i]=j;
				}
			}
		}
		else
		{
			int to=w;
			int now=w-1;
			for(int j=w-1;j>=0;j--)
			{
				if(l1[j][i+1]==-1) l1[j][i]=r1[j][i]=-1;
				else
				{
					now=min(now,r1[j][i+1]);
					for(;now>=l1[j][i+1];now--)
					{
						if(!use[i+1][now]||!use[i][now]) continue;
						else if(to>now)
						{
							to=now;
							while(to>0&&mp[i][to-1]!='#') to--;
						}
					}
					if(to>r1[j][i+1]) l1[j][i]=r1[j][i]=-1;
					else l1[j][i]=to;
				}
			}
			to=-1;
			now=0;
			for(int j=0;j<w;j++)
			{
				if(l1[j][i+1]==-1) l1[j][i]=r1[j][i]=-1;
				else
				{
					now=max(now,l1[j][i+1]);
					for(;now<=r1[j][i+1];now++)
					{
						if(!use[i+1][now]||!use[i][now]) continue;
						else to=now;
					}
					if(to<l1[j][i+1]) l1[j][i]=r1[j][i]=-1;
					else r1[j][i]=to;
				}
			}
		}
	}
	for(int i=m2;i<h;i++)
	{
		if(i==m2)
		{
			int now=-1;
			for(int j=w-1;j>=0;j--)
			{
				if(mp[i][j]=='#')
				{
					l2[j][i]=r2[j][i]=-1;
					now=-1;
				}
				else
				{
					if(now==-1) now=j;
					l2[j][i]=j;
					r2[j][i]=now;
				}
			}
		}
		else
		{
			int to=w;
			int now=w-1;
			for(int j=w-1;j>=0;j--)
			{
				if(l2[j][i-1]==-1) l2[j][i]=r2[j][i]=-1;
				else
				{
					now=min(now,r2[j][i-1]);
					for(;now>=l2[j][i-1];now--)
					{
						if(!use[i-1][now]||!use[i][now]) continue;
						else to=now;
					}
					if(to>r2[j][i-1]) l2[j][i]=r2[j][i]=-1;
					else l2[j][i]=to;
				}
			}
			to=-1;
			now=0;
			for(int j=0;j<w;j++)
			{
				if(l2[j][i-1]==-1) l2[j][i]=r2[j][i]=-1;
				else
				{
					now=max(now,l2[j][i-1]);
					for(;now<=r2[j][i-1];now++)
					{
						if(!use[i-1][now]||!use[i][now]) continue;
						else if(to<now)
						{
							to=now;
							while(to+1<w&&mp[i][to+1]!='#') to++;
						}
					}
					if(to<l2[j][i-1]) l2[j][i]=r2[j][i]=-1;
					else r2[j][i]=to;
				}
			}
		}
	}/*
	for(int i=0;i<w;i++)
	{
		for(int j=0;j<=m1;j++) printf("[%d %d] ",l1[i][j],r1[i][j]);puts("");
		for(int j=m2;j<h;j++) printf("[%d %d] ",l2[i][j],r2[i][j]);puts("");
	}*/
	for(int i=m2;i<h;i++) last[i]=-1;
	for(int i=0;i<w;i++)
	{
		for(int j=m2;j<h;j++)
		{
			if(l2[i][j]==-1) break;
			back[i][j]=last[j];
			nxt[i][j]=-1;
			if(last[j]!=-1) nxt[last[j]][j]=i;
			last[j]=i;
		}
	}
	for(int i=0;i<w;i++) bit[i].init(w+2);
	for(int i=0;i<w;i++)
	{
		for(int j=m2;j<h;j++)
		{
			if(l2[i][j]==-1) break;
			if(nxt[i][j]!=-1)
			{
				int to=nxt[i][j];
				if(l2[to][j]<=r2[i][j])
				{
					bit[i].add(to,get(j,l2[to][j],r2[i][j]));
					bit[to].add(i,get(j,l2[to][j],r2[i][j]));
				}
				//assert(l2[i][j]<=l2[to][j]);
				//assert(r2[i][j]<=r2[to][j]);
			}
		}
	}
	for(int i=m1;i>=0;i--)
	{
		for(int j=w-1;j>=0;j--)
		{
			if(!use[i][j]) ds[i][j]=dt[i][j]=-1;
			else
			{
				ds[i][j]=w,dt[i][j]=-1;
				if(i==m1) ds[i][j]=dt[i][j]=j;
				if(j+1<w&&use[i][j+1])
				{
					ds[i][j]=min(ds[i][j],ds[i][j+1]);
					dt[i][j]=max(dt[i][j],dt[i][j+1]);
				}
				if(i+1<=m1&&use[i+1][j])
				{
					ds[i][j]=min(ds[i][j],ds[i+1][j]);
					dt[i][j]=max(dt[i][j],dt[i+1][j]);
				}
			}
		}
	}
	vector <P> die;
	for(int i=0;i<w;i++)
	{
		for(int j=m1;j>=0;j--)
		{
			if(l1[i][j]==-1)
			{
				die.push_back(P(j,i));
				break;
			}
		}
		sd[i]=0;
		for(int j=m2;j<h;j++)
		{
			if(l2[i][j]==-1) break;
			sd[i]+=get(j,l2[i][j],r2[i][j]);
		}
		active[i]=true;
		//printf("* %d\n",sd[i]);
	}
	sort(die.begin(),die.end(),greater <P>());
	int pos=0;
	for(int i=m1;i>=0;i--)
	{
		while(pos<die.size()&&die[pos].first==i)
		{
			int v=die[pos++].second;
			active[v]=false;
			for(int j=m2;j<h;j++)
			{
				if(l2[v][j]==-1) break;
				int f=back[v][j],s=nxt[v][j];
				if(f!=-1)
				{
					nxt[f][j]=-1;
					if(l2[v][j]<=r2[f][j])
					{
						bit[f].add(v,-get(j,l2[v][j],r2[f][j]));
					}
				}
				if(s!=-1)
				{
					back[s][j]=-1;
					if(l2[s][j]<=r2[v][j])
					{
						bit[s].add(v,-get(j,l2[s][j],r2[v][j]));
					}
				}
				if(f!=-1&&s!=-1)
				{
					nxt[f][j]=s;
					back[s][j]=f;
					if(l2[s][j]<=r2[f][j])
					{
						bit[f].add(s,get(j,l2[s][j],r2[f][j]));
						bit[s].add(f,get(j,l2[s][j],r2[f][j]));
					}
				}
			}
		}
		int l=0,r=0;
		int sum=0;
		for(int j=0;j<w;j++)
		{
			if(!use[i][j]) continue;
			while(r<=dt[i][j])
			{
				if(active[r])
				{
					sum+=sd[r];
					sum-=bit[r].get(l,r);
				}
				r++;
			}
			while(l<ds[i][j])
			{
				if(active[l])
				{
					sum-=sd[l];
					sum+=bit[l].get(l,r);
				}
				l++;
			}
			ans+=(mp[i][j]-'0')*sum;
			//printf("%d %d : [%d %d] %d\n",i,j,ds[i][j],dt[i][j],sum);
		}
	}
	//printf("%lld\n",ans-AA);
	vector <string> S,T;
	for(int i=0;i<=m1;i++) S.push_back(mp[i]);
	for(int i=m2;i<h;i++) T.push_back(mp[i]);
	solve(S);
	solve(T);
}
bool NOW[SIZE][SIZE];
void naive(vector <string> mp)
{
	int n=mp.size(),m=mp[0].size();
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(mp[i][j]=='#') continue;
			for(int x=i;x<n;x++)
			{
				for(int y=j;y<m;y++)
				{
					if(mp[x][y]=='#') NOW[x][y]=false;
					else if(x==i&&y==j) NOW[x][y]=true;
					else
					{
						if(x>i&&NOW[x-1][y]) NOW[x][y]=true;
						else if(y>j&&NOW[x][y-1]) NOW[x][y]=true;
						else NOW[x][y]=false;
					}
					if((x!=i||y!=j)&&NOW[x][y]) ret+=(mp[i][j]-'0')*(mp[x][y]-'0');
				}
			}
		}
	}
	printf("%lld\n",ret);
}
int main()
{
	int n;
	scanf("%d",&n);
	vector <string> mp;
	for(int i=0;i<n;i++)
	{
		scanf("%s",&str);
		string S=str;
		mp.push_back(S);
	}
	ans=0;
	solve(mp);
	printf("%lld\n",ans);
	//naive(mp);
	return 0;
}