题目描述

$N$ 頂点単純無向グラフ $G$ が与えられます。

$G$ は $N$ 行 $N$ 列の隣接行列 $A$ によって与えられます。つまり、$A_{i,j}$ が $1$ である場合は頂点 $i,j$ 間に辺があることを、$0$ である場合には辺がないことを意味します。

$1\ \le\ i\ <\ j\ <\ k\ \le\ N$ を満たす整数の組 $(i,j,k)$ のうち、頂点 $i,j$ 間にも頂点 $j,k$ 間にも頂点 $i,k$ 間にも辺があるようなものの個数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_{1,1}A_{1,2}\dots\ A_{1,N}$ $A_{2,1}A_{2,2}\dots\ A_{2,N}$ $\vdots$ $A_{N,1}A_{N,2}\dots\ A_{N,N}$

输出格式

答えを出力せよ。

题目大意

给你一个简单的无向图，其中有 $N$ 个顶点。用一个 的 $N\times N$ 邻接矩阵 $A$ 来表示。如果 $A_{i,j}=1$ ,则表示 $i$ 到 $j$ 有边相连，如果 $A_{i,j}=0$ ,则表示 $i$ 到 $j$ 无边相连。

求三角形 $(i,j,k)$ 的个数，满足 $1\leq i < j < k\leq n$，且 $i$ 与 $j$ 有边相连，$i$ 与 $k$ 有边相连，$j$ 与 $k$ 有边相连。

4
0011
0011
1101
1110

2

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

0

提示

制約

• $3\ \le\ N\ \le\ 3000$
• $A$ は単純無向グラフ $G$ の隣接行列である。
• 入力はすべて整数。

Sample Explanation 1

$(i,j,k)=(1,3,4),(2,3,4)$ が条件を満たします。 $(i,j,k)=(1,2,3)$ は、頂点 $1,2$ 間に辺がないため条件を満たしません。 よって、解は $2$ です。