Description

A metric for measuring the connectivity of a directed graph is the reachability count, defined as the number of ordered pairs of vertices in which the second is reachable from the first.

As shown in the figure:

Vertex 1 can reach 1, 2, 3, 4, 5. Vertex 2 can reach 2, 3, 4, 5. Vertex 3 can reach 3, 4, 5. Vertices 4 and 5 can only reach themselves.

Therefore, the reachability count of this graph is $14$.

Given a graph, please compute its reachability count.

Input Format

The first line contains the number of vertices, a positive integer $N$.
Then follow $N$ lines, each containing $N$ characters. In the $i$-th row and $j$-th column, a 1 indicates there is a directed edge from $i$ to $j$, and 0 indicates no edge.

Output Format

Output a single line with one integer, the reachability count of the graph.

3
010
001
100

9

Hint

For $100\%$ of the testdata, $1 \le N \le 2000$.

Translated by ChatGPT 5