统计 L 形

题目描述

给定一个 $N \times N$ 的网格。用 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

格子中的内容由 $N$ 个长度为 $N$ 的字符串 $S_1, S_2, \dots, S_N$ 按如下方式给出:

• 若 $S_i$ 的第 $j$ 个字符为 o,则格子 $(i,j)$ 中写着 o。
• 若 $S_i$ 的第 $j$ 个字符为 x,则格子 $(i,j)$ 中写着 x。

求满足以下全部条件的格子三元组的个数:

• 三元组中的三个格子互不相同。
• 三个格子上都写着 o。
• 恰有两个格子在同一行。
• 恰有两个格子在同一列。

这里,两个三元组当且仅当某个格子恰好只被其中一个三元组包含时,才被认为是不同的。

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

以整数形式输出答案。

样例

3
ooo
oxx
xxo

4

以下四个三元组满足条件:

$(1,1),(1,2),(2,1)$

$(1,1),(1,3),(2,1)$

$(1,1),(1,3),(3,3)$

$(1,2),(1,3),(3,3)$

4
oxxx
xoxx
xxox
xxxo

0

15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

2960

数据范围

• $N$ 是 $2$ 到 $2000$ 之间的整数(含端点)
• $S_i$ 是由 o 和 x 组成的长度为 $N$ 的字符串