问题描述

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

我们有一个被分割成$N$个水平行和$N$个垂直列的正方形单元格的棋盘。从顶部到底部第$i$行和从左边到右边第$j$列的单元格称为$(i,j)$。每个单元格要么是空的，要么被障碍物占据。此外，每个空单元格上都写着一个数字。如果$A_{i,j}=$ 1、2、... 或者 9，那么单元格$(i,j)$为空，并且数字$A_{i,j}$写在上面。如果$A_{i,j}=$ #，则单元格$(i,j)$被障碍物占据。

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

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

考虑所有满足单元格$Y$可以从单元格$X$到达的单元格对$(X,Y)$。计算所有这些单元格对中，单元格$X$和单元格$Y$上的数字的乘积之和。

约束条件

• $1 \leq N \leq 1500$
• $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}$

输出

对于所有满足单元格$Y$可以从单元格$X$到达的单元格对$(X,Y)$，打印单元格$X$和单元格$Y$上的数字的乘积之和。

样例输入 1

2
11
11

样例输出 1

5

有五对满足单元格$Y$可以从单元格$X$到达的单元格$(X,Y)$，如下所示：

• $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)$

对于所有这些单元格对，单元格$X$和单元格$Y$上的数字的乘积都是$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