三角形

题目描述

给你一个具有 $N$ 个顶点的简单无向图 $G$。

$G$ 以 $N \times N$ 邻接矩阵 $A$ 给出。也就是说,当 $A_{i,j}$ 为 $1$ 时,顶点 $i$ 和顶点 $j$ 之间有边;为 $0$ 时则没有。

求满足 $1 \le i \lt j \lt k \le N$,且顶点 $i$ 与顶点 $j$ 之间有边、顶点 $j$ 与顶点 $k$ 之间有边、顶点 $i$ 与顶点 $k$ 之间有边的整数三元组 $(i,j,k)$ 的个数。

输入格式

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

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}

输出格式

输出答案。

样例

4
0011
0011
1101
1110

2

$(i,j,k)=(1,3,4),(2,3,4)$ 满足条件。

$(i,j,k)=(1,2,3)$ 不满足条件,因为顶点 $1$ 和顶点 $2$ 之间没有边。

因此,答案是 $2$。

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

0

数据范围

• $3 \le N \le 3000$
• $A$ 是简单无向图 $G$ 的邻接矩阵。
• 输入中的所有值均为整数。