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;
typedef long long ll;

const int M = 1505;

int n, l[M][M], r[M][M], gr[M][M];
bool reach[M][M];
char g[M][M];
ll ans;

void go(int i, int k) {
  int s = 0;
  int left = 0, right = -1;
  for (int j = 0; j < n; ++j) {
  // cout << l[k][j] << ' ' << r[k][j] << endl;
    if (r[k][j] == -1)
      continue;
    while (right < r[k][j]) {
      right++;
      if (reach[k][right])
        s += g[k][right];
    } while (left < l[k][j]) {
      if (reach[k][left])
        s -= g[k][left];
      left++;
    }
    ans += g[i][j]*s;
  }
  // cout << ans << endl;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      cin >> g[i][j];
      if (g[i][j] != '#')
        g[i][j] -= '0';
    }

  for (int i = 0; i < n; ++i)
    for (int j = n-1; j >= 0; --j) {
      if (g[i][j] == '#')
        gr[i][j] = -1;
      else
        gr[i][j] = max(j, gr[i][j+1]);
    }

  for (int i = 0; i < n; ++i) {
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    memset(reach, 0, sizeof(reach));
    for (int j = 0; j < n; ++j) {
      if (g[i][j] == '#') {
        r[i][j] = -1;
        l[i][j] = n;
        reach[i][j] = 0;
      } else {
        l[i][j] = j;
        r[i][j] = gr[i][j];
        reach[i][j] = 1;
      }
    }
    go(i, i);
    for (int k = i; k < n-1; ++k) {
      //update row k to row k+1
      for (int j = 0; j < n; ++j)
        if (g[k+1][j] != '#')
          reach[k+1][j] = reach[k][j];
      for (int j = 0; j < n-1; ++j)
        if (g[k+1][j+1] != '#')
          reach[k+1][j+1] |= reach[k+1][j];
      int right = -1, left = 0, best = -1, sz = 0;
      for (int j = 0; j < n; ++j) {
        if (r[k][j] == -1) {
          r[k+1][j] = -1;
          continue;
        }
        while (right < r[k][j]) {
          right++;
          if (!reach[k][right])
            continue;
          if (g[k+1][right] != '#') {
            best = gr[k+1][right];
            sz++;
          }
        } while (left < l[k][j]) {
          if (!reach[k][left]) {
            left++;
            continue;
          }
          if (g[k+1][left] != '#')
            sz--;
          left++;
        }
        if (sz == 0)
          r[k+1][j] = -1;
        else
          r[k+1][j] = best;
      }
      right = n-1, left = n, best = n, sz = 0;
      for (int j = n-1; j >= 0; --j) {
        if (r[k][j] == -1) {
          l[k+1][j] = n;
          continue;
        }
        while (left > l[k][j]) {
          left--;
          if (!reach[k][left])
            continue;
          if (g[k+1][left] != '#') {
            best = left;
            sz++;
          }
        } while (right > r[k][j]) {
          if (!reach[k][right]) {
            right--;
            continue;
          }
          if (g[k+1][right] != '#')
            sz--;
          right--;
        }
        if (sz == 0)
          l[k+1][j] = n;
        else
          l[k+1][j] = best;
      }
      go(i, k+1);
    }
  }

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (g[i][j] != '#')
        ans -= g[i][j]*g[i][j];
  cout << ans << endl;
}