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 optimize("O3")
#pragma GCC target("sse4.1")

#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n) for (int i = ((int)(n) - 1); i >= 0; --i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()

#ifdef LOCAL
#define eprintf(args...) fprintf(stderr, args), fflush(stderr);
#else
#define eprintf(args...) ;
#endif

const int mod = (int)1e9 + 7;

void add (int &a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}

void sub (int &a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
}

int mult (int a, int b)
{
    return (ll)a * b % mod;
}

int n;
vector<string> grid;

#ifdef LOCAL
//#define TEST
#endif // LOCAL

#ifndef TEST
bool read ()
{
    if (!(cin >> n))
        return false;

    grid.resize(n);
    forn (i, n)
        cin >> grid[i];

    return true;
}
#else
bool read ()
{
    n = 500;
    static mt19937 rng;

    grid = vector<string>(n, string(n, '#'));
    forn (i, n) forn (j, n)
        grid[i][j] = rng() % 9 + '1';

    return true;
}
#endif

using ull = unsigned long long;
const int bits = 64;

const int K = (1 << 16) - 1;
int prec[K + 1];

int popcnt (ull v)
{
    return prec[v & K] + prec[(v >> 16) & K] + prec[(v >> 32) & K] + prec[(v >> 48) & K];
}

struct bitarr
{
    vector<ull> v;
    int n;

    bitarr () {}

    bitarr (int len)
    {
        v.resize((len + bits) / bits);
        n = len;
    }

    int last () const
    {
        return int(v.back());
    }

    void or_with (const bitarr &o, const int bound)
    {
        assert(n == o.n);
        assert(sz(v) == sz(o.v));

        const int start = (bound >> 6);
        for (int i = start; i < sz(v); i++)
            v[i] |= o.v[i];
    }

    void reset ()
    {
        fill(all(v), ull(0));
    }

    void set (int pos)
    {
        v[pos >> 6] |= (1ULL << (pos & 63));
    }

    int bitcount () const
    {
        int ans = 0;
        forn (i, sz(v))
            ans += popcnt(v[i]);
        return ans;
    }
};

const int inf = int(1e9);

ll solve ()
{
    forn (i, K + 1)
        prec[i] = __builtin_popcount(i);

    const int digs = 9;

    vi cnt (digs);
    vvi id (n, vi(n, -1));

    forn (i, n) forn (j, n)
    {
        const int cur = grid[i][j] - '1';
        if (0 <= cur && cur < digs)
        {
            id[i][j] = cnt[cur];
            cnt[cur]++;
        }
    }

    vector<vector<vector<bitarr>>> dp (2, vector<vector<bitarr>>(n, vector<bitarr>(digs)));
    forn (c, 2) forn (i, n) forn (j, digs)
        dp[c][i][j] = bitarr(cnt[j]);

    int cur = 0;

    auto in = [&] (int x, int y) -> bool
    {
        return 0 <= x && x < n && 0 <= y && y < n && grid[x][y] != '#';
    };

    vector<vvi> lowest(n, vvi(n, vi(digs, inf)));

    ford (i, n) ford (j, n)
    {
        const int here = grid[i][j] - '1';
        if (0 <= here && here < digs)
            lowest[i][j][here] = id[i][j];

        forn (d, digs) forn (iter, 2) if (i + (iter == 0) < n && j + (iter == 1) < n)
            lowest[i][j][d] = min(lowest[i][j][d], lowest[i + (iter == 0)][j + (iter == 1)][d]);
    }

    ll ans = 0;
    ford (sum, 2 * n - 1)
    {
        const int prev = (cur ^ 1);

        forn (i, n)
        {
            const int j = sum - i;
            if (0 <= j && j < n)
            {
                forn (d, digs)
                    dp[cur][i][d].reset();

                if (in(i, j))
                {
                    const int here = grid[i][j] - '1';
                    assert(0 <= here && here < digs);

                    dp[cur][i][here].set(id[i][j]);

                    forn (iter, 2)
                    if (in (i + (iter == 0), j + (iter == 1)))
                    {
                        forn (d, digs)
                            dp[cur][i][d].or_with(dp[prev][i + (iter == 0)][d], lowest[i + (iter == 0)][j + (iter == 1)][d]);
                    }

//                    forn (d, digs)
//                        ans += dp[cur][i][d].last();
                    forn (d, digs)
                        ans += (d + 1) * (here + 1) * dp[cur][i][d].bitcount();
                    ans -= (here + 1) * (here + 1);
                }
            }
        }

        cur ^= 1;
    }

    return ans;
}

int32_t main()
{
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef TEST
    assert(read());
    auto ans = solve();
    cerr << ans << endl;
    return 0;
#endif // TEST

    while (read())
    {
        auto ans = solve();
        cout << ans << endl;
    }

    return 0;
}