小艾想数数一张无向图有多少哈密顿环。

哈密顿环 $C$ 是图 $G=(V,E)$ 的一个边集的子集 $C\subset E$，需要满足以下几个条件：

• 仅保留边集 $C$ 之后，$V$ 中每个顶点的度数均为 $2$。
• 仅保留边集 $C$ 之后，$V$ 中任意两个顶点是连通的。

这个问题还是挺简单的！小艾随便编了个 DP 就解决了这个问题。但是接着她发现了一个震惊的问题：她不知道怎么把一个数除以 $2$！

运算

你可能会很疑惑，自然数的除法不是很简单吗？事实上小艾处理的数并不是我们熟悉的自然数。我们详细说明小艾能做什么样的“运算”。

小艾能在一个定义了加法和乘法的集合 $R$ 上快速做计算。我们管在上面的加法和乘法叫做 $\oplus$ 和 $\otimes$。它满足我们所熟悉的运算律：

• 交换律，对于任意 $x,y\in R$，有加法交换律 $x\oplus y = y\oplus x$ 和乘法交换律 $x\otimes y = y\otimes x$。
• 结合律，对于任意 $x,y,z\in R$，有加法结合律 $(x\oplus y)\oplus z= x\oplus(y\oplus z)$ 和乘法结合律 $(x\otimes y)\otimes z= x\otimes(y\otimes z)$。
• 分配律，对于任意 $x,y,z\in R$，乘法对加法有分配律 $x\otimes (y\oplus z) = x\otimes y \oplus x\otimes z$。
• 单位元，有唯一元素 $0\in R$，满足任何 $x\in R$ 都有 $0\oplus x = x$，还有唯一元素 $1\in R$，满足任何 $x\in R$ 都有 $1\otimes x = x$。

为什么小艾不知道怎么除二呢？我们发现一个数的两倍在这里合适的定义应该是 $x\oplus x$，但在这里，我们的 $R$ 有一个额外的限制：对任何 $x\in R$，$x\oplus x=0$，因此知道一个数的两倍无法从中获取原数的任何信息。

举一个简单的例子：令 $R=\{0,1\}$，定义 $\oplus,\otimes$ 是 $\bmod 2$ 意义下的加法和乘法，那么 $R$ 就满足我们刚刚描述的所有性质。

这意味着小艾的算法中仍然可以正常地计算加法，乘法以及除以一个非零的数。

问题

现在我们来重新描述原问题。

给定一个完全无向图 $G$，定义上面每条边 $e=(i,j), i < j$ 有一个边权 $w(e)\in R$。我们定义一个哈密顿环 $C$ 的权值如下：设边集为 $\{e_1,e_2,\dots,e_n\}$，权值为边权的乘积 $w(e_1)\otimes w(e_2)\otimes\cdots \otimes w(e_n)$。我们要求的答案是所有哈密顿环 $C$ 的权值之和，这里的和是 $\oplus$ 的和。

实现

本题的实现中，我们选取的 $R$ 是一个叫做 Nimber 的域，且其中的数仅限定在 $32$ 位无符号整数，下发的 sample.cpp 附带了一个模板，内容为检验上述运算性质，你可以在确认了了解如何使用后将检验部分的代码删去，进行作答。其中 $x,y$ 的加法为异或运算，也即 C++ 中的 x ^ y，乘法需调用库中提供的函数 nimbers::product(x, y)。

我们保证，本题的标准解法并未用到 Nimber 本身相对于一般的 $R$ 的任何特殊性质。试图了解模板的实现细节或者 Nimber 的性质应该对解决本题没有额外帮助。

输入格式

第一行输入一个正整数 $n$，表示节点数。

接下来 $n$ 行每行 $n$ 个 $32$ 位无符号整数，第 $i$ 行第 $j$ 列为 $w(i,j)$，表示 $(i,j)$ 这条边的权值。保证 $w(i,i)=0, w(i,j)=w(j,i)$。

输出格式

输出一个 $32$ 位无符号整数，表示答案。

样例数据

样例 1 输入

3
0 1 1
1 0 1
1 1 0

样例 1 输出

1

样例 2 输入

4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0

样例 2 输出

5

样例 3 输入

5
0 872944379 561580851 495948204 3545905294
872944379 0 1882128761 362633209 4225914816
561580851 1882128761 0 1033434822 2849642680
495948204 362633209 1033434822 0 1837702960
3545905294 4225914816 2849642680 1837702960 0

样例 3 输出

1269688359

子任务

保证 $3\le n\le 20$。

对于第 $i(1\le i\le 5)$ 个测试点，保证 $n=i+2$。

对于第 $i(6\le i\le 10)$ 个测试点，保证 $n=i+10$。