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 target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
namespace whatever{
	int readu(){
		char ch=getchar();
		while(!isdigit(ch))
			ch=getchar();
		int value=ch-'0';
		ch=getchar();
		while(isdigit(ch)){
			value=value*10+ch-'0';
			ch=getchar();
		}
		return value;
	}
	void writeull(long long n){
		if(n<10)
			putchar(n+'0');
		else{
			writeull(n/10);
			putchar(n%10+'0');
		}
	}
	struct set_type{
		unsigned long long *data;
		int size;
		void clear(){
			memset(data, 0, sizeof(unsigned long long)*size);
		}
		void resize(int k){
			size=(k+63)/64;
			size=(size+3)/4*4;
			data=new unsigned long long [size];
			clear();
		}
		void operator=(const set_type &b){
			assert(size%4==0);
			assert(size==b.size);
			memcpy(data, b.data, sizeof(unsigned long long)*size);
		}
		void operator|=(const set_type &b){
			assert(size%4==0);
			assert(size==b.size);
			for(int i=0; i<size; i+=4){
				data[i]|=b.data[i];
				data[i+1]|=b.data[i+1];
				data[i+2]|=b.data[i+2];
				data[i+3]|=b.data[i+3];
			}
		}
		int count(){
			assert(size%4==0);
			int result=0;
			for(int i=0; i<size; i+=4){
				result+=__builtin_popcountll(data[i]);
				result+=__builtin_popcountll(data[i+1]);
				result+=__builtin_popcountll(data[i+2]);
				result+=__builtin_popcountll(data[i+3]);
			}
			return result;
		}
		void set(unsigned index){
			assert(size%4==0);
			assert(index<size*64);
			data[index/64]|=(1ull<<(index%64));
		}
	};
	void run(){
		int n=readu();
		static char a[500][502];
		for(int i=0; i<n; ++i)
			gets(a[i]);
		static int cnt[10];
		static int index[500][500];
		for(int i=0; i<n; ++i)
			for(int j=0; j<n; ++j)
				if(a[i][j]!='#'){
					assert(isdigit(a[i][j]));
					index[i][j]=cnt[a[i][j]-'0']++;
				}
		static set_type set_data[2][500][10];
		for(int i=0; i<2; ++i)
			for(int j=0; j<n; ++j)
				for(int k=0; k<10; ++k)
					set_data[i][j][k].resize(cnt[k]);
		set_type (*cur_set_data)[10]=set_data[0];
		set_type (*next_set_data)[10]=set_data[1];
		long long result=0;
		cerr<<"clock(): "<<clock()/double(CLOCKS_PER_SEC)<<endl;
		for(int r=n-1; r>=0; --r){
			for(int c=n-1; c>=0; --c){
				if(isdigit(a[r][c])){
					for(int i=0; i<10; ++i){
						next_set_data[c][i]=cur_set_data[c][i];
						if(c<n-1)
							next_set_data[c][i]|=next_set_data[c+1][i];
						result+=(long long)next_set_data[c][i].count()*i*(a[r][c]-'0');
						if(i==a[r][c]-'0')
							next_set_data[c][i].set(index[r][c]);
					}
				}
				else{
					for(int i=0; i<10; ++i)
						next_set_data[c][i].clear();
				}
			}
			swap(cur_set_data, next_set_data);
		}
		cerr<<"clock(): "<<clock()/double(CLOCKS_PER_SEC)<<endl;
		writeull(result);
		putchar('\n');
	}
}
int main(){
	whatever::run();
}