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 diagnostic ignored "-Wunused-result"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 502;
//const ll INF = (ll)1e18 + 41;
const int INF = (int)1e9 + 41;
const ll MD = (ll)1e9 + 7;
bool D = false;

int sum[N][N], a[N][N];
int max_depth[N][N];
short int r[N][N][N];
short int l[N][N][N];

void solve() {
    int n, m;
    cin >> n;
    m = n;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            a[i][j] = 0;
            max_depth[i][j] = i;
            sum[i][j] = 0;
            short int *r2 = r[i][j];
            short int *l2 = l[i][j];
            auto val_l = (short int)N;
            auto val_r = (short int)-1;
            for (int h = 0; h <= n; h++) {
                l2[h] = val_l;
                r2[h] = val_r;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '#') a[i][j] = 0;
            else a[i][j] = s[j] - '0';
        }
    }
    ll ans = 0;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (a[i][j] == 0) {
                max_depth[i][j] = -1;
                continue;
            }

            short int *left = r[i + 1][j];
            short int *_left = l[i + 1][j];
            short int *rait = l[i][j + 1];
            short int *_rait = r[i][j + 1];
            short int *meL = l[i][j];
            short int *meR = r[i][j];

            meL[i] = (short int)j;
            meR[i] = max(meL[i], _rait[i]);
            for (int h = i + 1; h < n; h++) {
                meL[h] = min(_left[h], rait[h]);
                meR[h] = max(left[h], _rait[h]);
            }
            max_depth[i][j] = max(i, max(max_depth[i + 1][j], max_depth[i][j + 1]));

            int cur_sum = sum[i][j + 1] + sum[i + 1][j];
            int h = i;
            //cout << i << " " << j << endl;
            if (i == 1 && j == 0) {
                j = i * j;
            }
            while (h < n) {
                while (h < n && left[h] < rait[h]) h++;
                if (h >= n) continue;

                cur_sum -= sum[h][rait[h]];
                h = max_depth[h][rait[h]] + 2;
            }

            sum[i][j] = cur_sum + a[i][j];
            ans += a[i][j] * cur_sum;
        }
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tst = 1;
    //scanf("%d", &tst);
    //cin >> tst;
#ifdef MADE_BY_SERT
    //freopen("a.in", "r", stdin);
    D = true;
    tst = 4;
    while (tst--) {
        solve();
    }
#else
    while (tst--) solve();
#endif
}