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 <cstdio>
#include <unordered_map>
#include <bitset>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define _ << " " <<

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAX = 1505;
const ull H = 2342311;
const ull MOD = 1e9 + 7;

int brred, brstup;
int p[2][MAX][MAX];

ll sum_sq(int r, int s1, int s2, int st) {
  ll ret=0;
  FOR(j, s1, s2+1)
    ret += p[st][r][j] * p[st][r][j];
  return ret;
}

ll calc_single(int r, int s1, int s2, int st) {
  ll sum=0, ret=0;
  FOR(j, s1, s2+1) {
    if (!p[st][r][j]) {
      sum = 0;
      continue;
    }

    ret += p[st][r][j] * sum;
    sum += p[st][r][j];
  }

  return ret;
}

ull Bgor[MAX][MAX][MAX/64+1], Bdol[MAX][MAX][MAX/64+1];
int SZ;

void reset(ull B[MAX][MAX][MAX/64+1], int r1, int r2, int s1, int s2) {
  FOR(i, r1, r2+1) FOR(j, s1, s2+1) REP(k, SZ)
    B[i][j][k] = 0;
}

void andaj(ull a[], ull b[], ull c[]) {
  REP(i, SZ) c[i] = a[i] & b[i];
}

void oraj(ull a[], ull b[], ull c[]) {
  REP(i, SZ) c[i] = a[i] | b[i];
}

void kopiraj(ull a[], ull b[]) {
  REP(i, SZ) b[i] = a[i];
}

void stavi(ull a[], int ind) {
  a[ind/64] |= ((ull) 1) << (ind % 64);
}

bool notempty(ull a[]) {
  REP(i, SZ) if (a[i]) return true;
  return false;
}

ull get_h(ull a[]) {
  ull r=0;
  REP(i, SZ) r = ((r*H)%MOD + (a[i]%MOD))%MOD;
  return r;
}

void go_down(int r1, int r2, int s1, int s2, int st) {
  reset(Bgor, r1, r2, s1, s2);

  for (int i=r2; i>=r1; i--) {
    for (int j=s2; j>=s1; j--) {
      if (!p[st][i][j]) continue;
      if (i != r2 && j != s2) oraj(Bgor[i+1][j], Bgor[i][j+1], Bgor[i][j]);
      else if (i != r2) kopiraj(Bgor[i+1][j], Bgor[i][j]);
      else if (j != s2) kopiraj(Bgor[i][j+1], Bgor[i][j]);

      if (i == r2) stavi(Bgor[i][j], j-s1);
    }
  }
}

void go_up(int r1, int r2, int s1, int s2, int st) {
  reset(Bdol, r1, r2, s1, s2);

  FOR(i, r1, r2+1) {
    FOR(j, s1, s2+1) {
      if (!p[st][i][j]) continue;
      if (i != r1 && j != s1) oraj(Bdol[i-1][j], Bdol[i][j-1], Bdol[i][j]);
      else if (i != r1) kopiraj(Bdol[i-1][j], Bdol[i][j]);
      else if (j != s1) kopiraj(Bdol[i][j-1], Bdol[i][j]);

      if (i == r1) stavi(Bdol[i][j], j-s1);
    }
  }
}

ull tmp[MAX/64+1];
ll spoji(int r1, int mid, int r2, int s1, int s2, int st) {
  unordered_map <ull, ll> Sum_dol, Sum_gor;
  unordered_map <ull, P> Pred_dol, Pred_gor;

  FOR(i, r1, mid+1) {
    FOR(j, s1, s2+1) {
      ull h = get_h(Bgor[i][j]);
      Pred_gor[h] = P(i, j);
      Sum_gor[h] += p[st][i][j];
    }
  }

  FOR(i, mid, r2+1) {
    FOR(j, s1, s2+1) {
      ull h = get_h(Bdol[i][j]);
      Pred_dol[h] = P(i, j);
      Sum_dol[h] += p[st][i][j];
    }
  }

  ll ret=0;
  for (auto gor = Pred_gor.begin(); gor != Pred_gor.end(); gor++) {
    for (auto dol = Pred_dol.begin(); dol != Pred_dol.end(); dol++) {
      andaj(Bgor[gor->Y.X][gor->Y.Y], Bdol[dol->Y.X][dol->Y.Y], tmp);
      if (notempty(tmp))
        ret += Sum_gor[gor->X] * Sum_dol[dol->X];
    }
  }

  return ret;
}

ll calc(int r1, int r2, int s1, int s2, int st) {
  if (r1 > r2 || s1 > s2) return 0;
  if (r2-r1 < s2-s1)
    return calc(s1, s2, r1, r2, 1^st);

  if (r1 == r2)
    return calc_single(r1, s1, s2, st);

  int mid = (r1 + r2) / 2;
  SZ = (s2 - s1 + 64) / 64;

  go_down(r1, mid, s1, s2, st);
  go_up(mid, r2, s1, s2, st);

  ll ret = spoji(r1, mid, r2, s1, s2, st);

  ret -= sum_sq(mid, s1, s2, st);

  ret += calc(r1, mid-1, s1, s2, st);
  ret += calc(mid+1, r2, s1, s2, st);

  return ret;
}

char s[MAX][MAX];

int main()
{
  int n;
  scanf("%d", &n);

  REP(i, n) {
    scanf(" %s", s[i]);
    REP(j, n)
      p[0][i][j] = p[1][j][i] = (s[i][j] == '#' ? 0 : (int) (s[i][j] - '0'));
  }

  printf("%lld\n", calc(0, n-1, 0, n-1, 0));

  return 0;
}