19360번 - Walk of Length 6 다국어

문제

Bobo has an undirected graph with $n$ vertices which are conveniently labeled with 1,ドル 2, \dots, n$. Let $V$ be the set of vertices and $E$ be the set of edges. He would like to count the number of tuples $(v_1, v_2, \dots, v_6)$ where:

• $v_1, v_2, \dots, v_6 \in V,ドル
• $\{v_1, v_2\}, \{v_2, v_3\}, \dots, \{v_5, v_6\}, \{v_6, v_1\} \in E$;
• $\mathcal{C} = (\{v_1, v_2\}, \{v_2, v_3\}, \dots, \{v_5, v_6\}, \{v_6, v_1\})$ is not a simple cycle of length 6ドル$.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains an integer $n$ (1ドル \leq n \leq 1000$).

The $i$-th of the following $n$ lines contains a string $g_i$ of length $n$ where $g_{i, j}$ denotes the existence of edge $\{i, j\}$ ($g_{i, j} \in \{0, 1\},ドル $g_{i, i} = 0,ドル $g_{i, j} = g_{j, i}$).

It is guaranteed that the sum of $n$ does not exceed 1000ドル$.

출력

For each test case, output an integer which denotes the number of tuples.

제한

힌트