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;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char *s) {
  return to_string((string)s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template<typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<typename A> string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() {
  cerr << endl;
}

template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

const int inf = 0x3f3f3f3f;

void cmax(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void cmin(int &x, int y) {
  if (x > y) {
    x = y;
  }
}

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector<string> board(n);
  for (int i = 0; i < n; ++i) {
    cin >> board[i];
  }
  long long answer = 0;

  function<void(vector<string>)> solve = [&](vector<string> board) {
    int n = board.size(), m = board[0].size();
    
    if (n < m) {
      vector<string> rotated(m, string(n, ' '));
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          rotated[j][i] = board[i][j];
        }
      }
      swap(n, m);
      board = rotated;
    }
    
    if (m == 1) {
      int sum = 0;
      for (int i = 0; i < n; ++i) {
        if (board[i][0] == '#') {
          sum = 0;
        } else {
          answer += (board[i][0] - '0') * sum;
          sum += board[i][0] - '0';
        }
      }
      return;
    }

    vector<string> u = vector<string> (board.begin(), board.begin() + (n >> 1));
    vector<string> d = vector<string> (board.begin() + (n >> 1), board.end());
    solve(u);
    solve(d);
    u.push_back(d[0]);

    int nu = n >> 1, nd = n + 1 >> 1;
    vector<vector<int>> left(nd, vector<int> (m, inf));
    vector<vector<int>> right(nd, vector<int> (m, -inf));
    vector<int> top(m);
    vector<int> bottom(m);
    for (int i = 0; i < m; ++i) {
      if (d[0][i] != '#') {
        left[0][i] = right[0][i] = i;
      }
    }
    for (int i = 0; i < nd; ++i) {
      for (int j = 0; j < m; ++j) {
        if (d[i][j] != '#') {
          if (i) {
            cmin(left[i][j], left[i - 1][j]);
            cmax(right[i][j], right[i - 1][j]);
          }
          if (j) {
            cmin(left[i][j], left[i][j - 1]);
            cmax(right[i][j], right[i][j - 1]);
          }
        }
      }
    }

    {
      vector<vector<int>> temp(nd, vector<int> (m, -inf));
      for (int i = nd - 1; ~i; --i) {
        for (int j = m - 1; ~j; --j) {
          if (d[i][j] != '#') {
            temp[i][j] = i;
            if (i + 1 < nd) {
              cmax(temp[i][j], temp[i + 1][j]);
            }
            if (j + 1 < m) {
              cmax(temp[i][j], temp[i][j + 1]);
            }
          }
        }
      }
      for (int i = 0; i < m; ++i) {
        bottom[i] = temp[0][i];
      }
    }

    {
      vector<vector<int>> temp(nu + 1, vector<int> (m, inf));
      for (int i = 0; i <= nu; ++i) {
        for (int j = 0; j < m; ++j) {
          if (u[i][j] != '#') {
            temp[i][j] = i;
            if (i) {
              cmin(temp[i][j], temp[i - 1][j]);
            }
            if (j) {
              cmin(temp[i][j], temp[i][j - 1]);
            }
          }
        }
      }
      for (int i = 0; i < m; ++i) {
        top[i] = temp[nu][i];
      }
    }

    vector<vector<int>> mp(m, vector<int> (m, inf));
    for (int i = 0; i < nd; ++i) {
      for (int j = 0; j < m; ++j) {
        if (left[i][j] <= right[i][j]) {
          cmin(mp[left[i][j]][right[i][j]], i);
        }
      }
    }
    for (int l = 0; l < m; ++l) {
      for (int r = m - 1; ~r; --r) {
        if (l) {
          cmin(mp[l][r], mp[l - 1][r]);
        }
        if (r + 1 < m) {
          cmin(mp[l][r], mp[l][r + 1]);
        }
      }
    }

    auto meeting_point = [&](int a, int b) {
      int p = mp[a][b];
      return p <= min(bottom[a], bottom[b]) ? p : inf;
    };

    vector<int> sum1(nd);
    vector<vector<int>> sum2(nd, vector<int> (m));
    vector<vector<int>> sum3(nd, vector<int> (m));
    vector<vector<int>> sum4(m, vector<int> (m));

    for (int i = 0; i < nd; ++i) {
      if (i) {
        sum1[i] = sum1[i - 1];
        for (int j = 0; j < m; ++j) {
          sum2[i][j] = sum2[i - 1][j];
          sum3[i][j] = sum3[i - 1][j];
        }
      }
      for (int j = 0; j < m; ++j) {
        if (left[i][j] <= right[i][j]) {
          sum1[i] += d[i][j] - '0';
          if (left[i][j]) {
            sum2[i][left[i][j] - 1] += d[i][j] - '0';
          }
          if (right[i][j] + 1 < m) {
            sum3[i][right[i][j] + 1] += d[i][j] - '0';
          }
          if (left[i][j] && right[i][j] + 1 < m) {
            sum4[left[i][j] - 1][right[i][j] + 1] += d[i][j] - '0';
          }
        }
      }
    }
    for (int i = 0; i < nd; ++i) {
      for (int j = m - 1; j; --j) {
        sum2[i][j - 1] += sum2[i][j];
      }
      for (int j = 1; j < m; ++j) {
        sum3[i][j] += sum3[i][j - 1];
      }
    }
    for (int l = m - 1; ~l; --l) {
      for (int r = l; r < m; ++r) {
        if (l + 1 < m) {
          sum4[l][r] += sum4[l + 1][r];
        }
        if (r) {
          sum4[l][r] += sum4[l][r - 1];
        }
        if (l + 1 < m && r) {
          sum4[l][r] -= sum4[l + 1][r - 1];
        }
      }
    }

    auto both_reachable = [&](int a, int b, int l) {
      if (meeting_point(a, b) > l) {
        return 0;
      } else {
        return sum1[l] - sum2[l][a] - sum3[l][b] + sum4[a][b];
      }
    };

    vector<int> reachable(m);
    for (int i = 0; i < m; ++i) {
      reachable[i] = both_reachable(i, i, bottom[i]);
    }

    vector<vector<int>> event(nu);
    vector<bool> ban(m);
    for (int i = 0; i < m; ++i) {
      if (top[i] >= nu) {
        ban[i] = true;
      } else {
        event[top[i]].push_back(i);
      }
    }
    vector<int> l(m), r(m);
    for (int i = m - 1; ~i; --i) {
      if (d[0][i] == '#') {
        l[i] = inf;
        r[i] = -inf;
      } else {
        l[i] = i;
        r[i] = max(i, i + 1 < m ? r[i + 1] : -inf);
      }
    }
    for (int row = nu - 1; ~row; --row) {
      for (int i = m - 1; ~i; --i) {
        if (u[row][i] == '#') {
          l[i] = inf;
          r[i] = -inf;
        } else if (i + 1 < m) {
          cmin(l[i], l[i + 1]);
          cmax(r[i], r[i + 1]);
        }
      }
      vector<int> has(m);
      vector<int> st(m);
      int sum = 0, stl = 0, str = 0, myl = 0, myr = -1;
      
      auto insert = [&](int x) {
        if (!ban[x]) {
          if (stl < str) {
            sum -= has[st[str - 1]];
            has[st[str - 1]] -= both_reachable(st[str - 1], x, min(bottom[st[str - 1]], bottom[x]));
            sum += has[st[str - 1]];
            if (bottom[st[str - 1]] <= bottom[x]) {
              --str;
              while (stl < str) {
                sum -= has[st[str - 1]];
                has[st[str - 1]] -= both_reachable(st[str - 1], x, min(bottom[st[str - 1]], bottom[x])) - both_reachable(st[str - 1], x, min(bottom[st[str]], bottom[x]));
                sum += has[st[str - 1]];
                if (bottom[st[str - 1]] <= bottom[x]) {
                  --str;
                } else {
                  break;
                }
              }
            }
          }
          st[str++] = x;
          has[x] = reachable[x];
          sum += has[x];
        }
      };

      auto erase = [&](int x) {
        if (!ban[x]) {
          sum -= has[x];
          if (stl < str && st[stl] == x) {
            ++stl;
          }
        }
      };

      for (int i = 0; i < m; ++i) {
        if (l[i] <= r[i]) {
          while (myr < r[i]) {
            insert(++myr);
          }
          while (myl < l[i]) {
            erase(myl++);
          }
          answer += (u[row][i] - '0') * sum;
        }
      }
      for (auto p : event[row]) {
        ban[p] = true;
      }
    }
  };

  solve(board);
  cout << answer << endl;
  return 0;
}