题目描述

问题F和F2是相同的问题，但约束条件和时间限制不同。

我们有一个被分割成 $N$ 个水平行和 $N$ 个垂直列方格单元的棋盘。位于从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格称为 Cell $(i,j)$。每个单元格要么为空，要么被障碍物占据。此外，每个空单元格上都写着一个数字。如果 $A_{i,j}=$ 1, 2, ... 或 9，则 Cell $(i,j)$ 为空，并且数字 $A_{i,j}$ 写在其上。如果 $A_{i,j}=$ #，则 Cell $(i,j)$ 被障碍物占据。

当满足以下条件时，从单元格 $X$ 可以到达单元格 $Y$：

• 单元格 $X$ 和 $Y$ 不同。
• 单元格 $X$ 和 $Y$ 都是空的。
• 可以通过重复向右或向下移动到相邻的空单元格，从单元格 $X$ 到达单元格 $Y$。

考虑所有满足 cell $Y$ 从 cell $X$ 可达的单元格对 $(X,Y)$。找出所有这些单元格对上写的数字乘积的总和。

约束条件

• $1 \leq N \leq 500$
• $A_{i,j}$ 是以下字符之一: 1, 2, ... 9 和 #。

输入

从标准输入读入输入数据，输入格式如下：

$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}$

输出

对于所有满足 cell $Y$ 从 cell $X$ 可达的单元格对 $(X,Y)$，输出所写数字的乘积的总和。

示例输入1

2
11
11

示例输出1

5

存在五个单元格对 $(X,Y)$ 满足 cell $Y$ 从 cell $X$ 可达，如下所示：

• $X=(1,1)$，$Y=(1,2)$
• $X=(1,1)$，$Y=(2,1)$
• $X=(1,1)$，$Y=(2,2)$
• $X=(1,2)$，$Y=(2,2)$
• $X=(2,1)$，$Y=(2,2)$

所有这些单元格对上写的数字乘积都是 $1$，因此答案是 $5$。

示例输入2

4
1111
11#1
1#11
1111

示例输出2

47

示例输入3

10
76##63##3#
8445669721
75#9542133
3#285##445
749632##89
2458##9515
5952578#77
1#3#44196#
4355#99#1#
#298#63587

示例输出3

36065

示例输入4

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#########

示例输出4

6525