CF1338E.JYPnation

Due to the success of TWICE, JYP Entertainment has earned countless money and emerged as the biggest entertainment firm by market capitalization. Therefore, the boss, JYP, has decided to create a new nation and has appointed you to provide a design diagram.

The new nation consists of $n$ cities and some roads between them. JYP has given some restrictions:

• To guarantee efficiency while avoiding chaos, for any $2$ different cities $A$ and $B$, there is exactly one road between them, and it is one-directional. There are no roads connecting a city to itself.

• The logo of rivaling companies should not appear in the plan, that is, there does not exist $4$ distinct cities $A$,$B$,$C$,$D$ , such that the following configuration occurs.

JYP has given criteria for your diagram. For two cities $A$,$B$, let $dis(A,B)$ be the smallest number of roads you have to go through to get from $A$ to $B$. If it is not possible to walk from $A$ to $B$, $dis(A,B) = 614n$. Then, the efficiency value is defined to be the sum of $dis(A,B)$ for all ordered pairs of distinct cities $(A,B)$.

Note that $dis(A,B)$ doesn't have to be equal to $dis(B,A)$.

You have drawn a design diagram that satisfies JYP's restrictions. Find the sum of $dis(A,B)$ over all ordered pairs of cities $(A,B)$ with $A\neq B$.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.

由于TWICE的成功，JYP娱乐公司已赚取了巨额财富，并一跃成为市值最高的娱乐公司。因此，老板JYP决定创建一个新国家，并任命你为其提供一份设计图。

该新国家由 $n$ 座城市及它们之间的一些道路组成。JYP给出了如下限制条件：

• 为保障效率并避免混乱，对任意两个不同的城市 $A$ 和 $B$，其间恰好存在一条单向道路；不存在从某城市通往其自身的道路。

• 设计图中不得出现竞争对手公司的标志，即：不存在四个互不相同的城市 $A$、$B$、$C$、$D$，使得如下构型出现：

JYP还为你的设计图设定了评估标准。对任意两座城市 $A$、$B$，定义 $dis(A,B)$ 为从 $A$ 到 $B$ 所需经过的最少道路条数；若无法从 $A$ 到达 $B$，则令 $dis(A,B) = 614n$。于是，效率值被定义为所有满足 $A \neq B$ 的有序城市对 $(A,B)$ 对应的 $dis(A,B)$ 之和。

注意：$dis(A,B)$ 不一定等于 $dis(B,A)$。

你已绘制出一幅满足JYP全部限制条件的设计图。请计算所有满足 $A \neq B$ 的有序城市对 $(A,B)$ 对应的 $dis(A,B)$ 之和。

注意：输入以压缩形式给出。尽管如此，你仍应使用快速输入方式。

The first line contains a single integer $n$ ($4 \le n \le 8000$, $n \equiv 0 \pmod{4}$) — the number of cities.

A binary matrix is encrypted in the following format. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are $1011$, and if the number is $5$, then the corresponding elements are $0101$.

After you obtain the decrypted binary matrix, the $j$-th character of the $i$-th row is $1$ if the one-directional road between cities $i$ and $j$ is directed from $i$ to $j$, and $0$ otherwise. It is guaranteed that the graph satisfies the restrictions mentioned above.

第一行包含一个整数 $n$（$4 \le n \le 8000$，且 $n \equiv 0 \pmod{4}$），表示城市的数量。

接下来以如下格式给出一个二进制矩阵：随后的 $n$ 行中，每行包含 $\frac{n}{4}$ 个一位十六进制数字（即这些数字可表示为数字 $0$ 至 $9$ 或大写拉丁字母 $A$ 至 $F$）。每个十六进制数字的二进制表示对应矩阵中该行的接下来 $4$ 个元素。例如，若给出数字 $B$，则对应的四个元素为 $1011$；若给出数字 $5$，则对应的四个元素为 $0101$。

在你解密得到该二进制矩阵后，第 $i$ 行的第 $j$ 个字符为 $1$ 当且仅当存在一条从城市 $i$ 指向城市 $j$ 的有向道路；否则为 $0$。题目保证该图满足上述所有限制条件。

Output one integer, representing the sum of $dis(A,B)$ over all ordered pairs of cities $(A,B)$ with $A\neq B$.

输出一个整数，表示对所有满足 $A\neq B$ 的有序城市对 $(A,B)$ 的 $dis(A,B)$ 之和。

The first example corresponds to the matrix:

$\begin{matrix} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \end{matrix}$

Which corresponds to this graph:

$dis(1,2)=dis(1,3)=dis(1,4)=dis(2,3)=dis(3,4)=dis(4,2)=1$

$dis(2,4)=dis(4,3)=dis(3,2)=2$

$dis(2,1)=dis(3,1)=dis(4,1)=2456$

Therefore the answer for the diagram is $7380$.

第一个示例对应如下矩阵：

$\begin{matrix} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \end{matrix}$

该矩阵对应的图如下：

$dis(1,2)=dis(1,3)=dis(1,4)=dis(2,3)=dis(3,4)=dis(4,2)=1$

$dis(2,4)=dis(4,3)=dis(3,2)=2$

$dis(2,1)=dis(3,1)=dis(4,1)=2456$

因此，该图的答案为 $7380$。