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;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin (),(x).end()
#define sqrt(x) sqrt(abs(x))
#define re return
#define sz(x) ((int)(x).size ())
#define prev PREV
#define next NEXT

using ll = long long;
using ii = pair<int, int>;
using ld = long double;
using D = double;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vs = vector<string>;

template<typename T> T abs (T x) { re x < 0 ? -x : x; }
template<typename T> T sgn (T x) { re x < 0 ? -1 : (x > 0 ? 1 : 0); }
template<typename T> T sqr (T x) { re x * x; }
template<typename T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }

const int N = 500;

int n;
int m;
ll ans = 0;
int g[N][N];
ii q[N * N];
int used[N][N];
int was[N][N];
int cur;
int l, r;

int go (int i, int j) {
	if (i >= n || j >= n || g[i][j] == 0 || was[i][j]) re 0;
	was[i][j] = 1;
	int cr = r;
	q[r++] = mp (i, j);
	used[i][j] = 1;
	while (l < r) {
		int x = q[l].fi;
		int y = q[l].se;
//		printf ("add %d %d\n", x, y);
		cur += g[x][y];
		l++;
		for (int t = 0; t < 2; t++) {
			int nx = x - int (t == 0);
			int ny = y - int (t == 1);
			if (nx >= 0 && ny >= 0 && !used[nx][ny] && g[nx][ny] > 0) {
				q[r++] = mp (nx, ny);
				used[nx][ny] = 1;
			}
		}
	}
//	printf ("%d %d = %d\n", i, j, cur);
	ans += (ll)(cur - g[i][j]) * g[i][j];
	go (i, j + 1);
	go (i + 1, j);
	while (r > cr) {
		r--;
		int x = q[r].fi;
		int y = q[r].se;
//		printf ("del %d %d\n", x, y);
		cur -= g[x][y]; 
		used[x][y] = 0;
	}
	l = r;
//	printf ("%d %d = %d\n", i, j, cur);
	re 0;
}

int main () {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
			if (s[j] == '#')
				g[i][j] = 0;
			else
				g[i][j] = s[j] - '0';	
	}	
	l = r = 0;
	cur = 0;
	ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (!was[i][j] && g[i][j] > 0)
				go (i, j);
	cout << ans << endl;
	cerr << clock () << endl;
	return 0;
}