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;

struct Bitset {
  vector<unsigned long long> a;
  Bitset() {}
  Bitset(const vector<unsigned long long>& a) : a(a) {}

  Bitset f(const Bitset &o) {
    vector<unsigned long long> vec(max(o.a.size(), a.size()));
    for (int i = 0; i < vec.size(); i++) {
      unsigned long long x = 0, y = 0;
      if (i < a.size()) x = a[i];
      if (i < o.a.size()) y = o.a[i];
      vec[i] = (x | y);
    }
    return Bitset(vec);
  }

  int count() {
    int ret = 0;
    for (auto x : a) {
      ret += __builtin_popcountll(x);
    }
    return ret;
  }

  void reset() {
    for (auto& x : a) {
      x = 0;
    }
  }

  void set(int v) {
    int p = v / 64;
    while (a.size() <= p) a.push_back(0);
    a[p] |= (1ULL << (v % 64));
  }
}a[2][501][10];

int main(int argc, char *argv[]) {
  std::ios_base::sync_with_stdio(false);
  vector<int> c(11);
  int n;
  cin >> n;
  long long ans = 0;
  for (int i = 0, now = 0; i < n; i++, now ^= 1) {
    for (int j = 1; j <= n; j++) {
      for (int k = 1; k <= 9; k++) {
        a[now][j][k].reset();
      }
    }
    string s;
    cin >> s;
    for (int j = 1; j <= n; j++) {
      if (s[j - 1] == '#') continue;
      int v = s[j - 1] - '0';
      for (int k = 1; k <= 9; k++) {
        a[now][j][k] = a[now][j - 1][k].f(a[now ^ 1][j][k]);
        ans += a[now][j][k].count() * k * v;
      }
      a[now][j][v].set(c[v]++);
    }
  }
  cout << ans << endl;
  return 0;
}