시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

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.

예제 입력 1

3
011
101
110
4
0101
1010
0101
1010
6
011111
101111
110111
111011
111101
111110

예제 출력 1

66
128
14910