题目描述

给你一个包含 $n$ 个顶点的有向图。顶点编号从 $1$ 到 $n$。

我们用一个 $n \times n$ 的二维数字矩阵 $g$ 表示这个有向图，该矩阵中第 $i$ 行第 $j$ 列的数字表示为 $g_{i,j}$。

• 如果 $g_{i, j} = 1$，则表示存在一条从顶点 $i$ 连向顶点 $j$ 的有向边；
• 如果 $g_{i, j} = 0$，则表示不存在从顶点 $i$ 连向顶点 $j$ 的有向边。

如果存在三个整数 $i, j, k$ 同时满足以下所有条件：

1. $1 \le i \lt j \lt k \le n$；
2. $g_{i,j} = 1$；
3. $g_{j,k} = 1$；
4. $g_{k,i} = 1$

则我们称三元组 $(i, j, k)$ 构成一个三元环。

求：图中三元环个数。

输入格式

第一行，一个整数 $n$。

接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行的第 $j$ 个整数表示 $g_{i, j}$。同一行相邻整数间以一个空格分隔。

输出格式

输出一个整数，表示图中三元环的个数。

样例

3
0 1 0
0 0 1
1 0 0

1

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

4

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 20$
• 对于 $40\%$ 的数据，$n \le 200$
• 对于 $100\%$ 的数据，$3 \le n \le 2000$，$0 \le g_{i, j} \le 1$，$g_{i,i} = 0(1 \le i \le n)$