小艾は無向グラフに含まれるハミルトン閉路の数を数えたいと考えています。

ハミルトン閉路 $C$ とは、グラフ $G=(V,E)$ の辺集合の部分集合 $C\subset E$ であり、以下の条件を満たすものです。

• 辺集合 $C$ のみを残したとき、$V$ の各頂点の次数はすべて $2$ である。
• 辺集合 $C$ のみを残したとき、$V$ の任意の $2$ 頂点は連結である。

この問題は非常に単純です！小艾は適当な 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\oplus x = x$ を満たす唯一の元 $0\in R$ が存在し、$1\otimes x = x$ を満たす唯一の元 $1\in R$ が存在する。

なぜ小艾は $2$ で割る方法を知らないのでしょうか？ある数の $2$ 倍は $x\oplus x$ と定義されるべきですが、ここでの $R$ には追加の制限があります。すべての $x\in R$ に対して $x\oplus x=0$ が成り立つため、ある数の $2$ 倍を知っても、元の数に関する情報を得ることはできません。

簡単な例を挙げます：$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$ の加法は排他的論理和（XOR）、すなわち C++ の x ^ y であり、乗法はライブラリが提供する関数 nimbers::product(x, y) を呼び出す必要があります。

本問題の標準的な解法において、Nimber 自体が持つ一般的な $R$ とは異なる特殊な性質は一切使用しないことを保証します。テンプレートの実装詳細や Nimber の性質を理解しようとすることは、本問題を解く上で何の助けにもなりません。

入力

入力は以下の形式で与えられる。

$n$ $w(1,1) \dots w(1,n)$ $\vdots$ $w(n,1) \dots w(n,n)$

$n$ は頂点数。 続く $n$ 行にはそれぞれ $n$ 個の $32$ ビット符号なし整数が与えられ、$i$ 行 $j$ 列目は辺 $(i,j)$ の重み $w(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

サンプル 2

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

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

1269688359

サブタスク

$3\le n\le 20$ を満たす。

• テストケース $i (1\le i\le 5)$ において、$n=i+2$ を満たす。
• テストケース $i (6\le i\le 10)$ において、$n=i+10$ を満たす。