题目描述

给定一个简单的无向图G，其中包含N个顶点。

G以N×N的邻接矩阵A给出。也就是说，如果A_{i,j}为1，则顶点i和j之间有一条边，如果A_{i,j}为0，则没有边。

找出满足$1 \le i < j < k \le N$且顶点i和j之间有一条边，顶点j和k之间有一条边，顶点i和k之间有一条边的整数三元组$(i,j,k)$的数量。

约束条件

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

输入

输入格式如下：

$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}$

输出

打印输出答案。

示例输入1

4
0011
0011
1101
1110

示例输出1

2

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

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

因此，答案是2。

示例输入2

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

示例输出2

0