题目描述

给你一个简单的无向图，其中有 $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$ 有边相连。

输入格式

第一行输入一个整数 $N$

接下来 $N$ 行，每行 $N$ 个字符要么是 $1$ 要么是 $0$。$A_{i,j}=1$ 说明 $i$ 到 $j$ 有无向边。否则没有。

输出格式

输出一个整数代表答案

4
0011
0011
1101
1110

2

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

0

提示

• $3\ \le\ N\ \le\ 3000$

样例 1 解释

$(i,j,k)=(1,3,4),(2,3,4)$ 这两个三元组符合要求。