Сяо Ай хочет посчитать количество гамильтоновых циклов в неориентированном графе.

Гамильтонов цикл $C$ — это подмножество ребер $C \subset E$ графа $G=(V,E)$, удовлетворяющее следующим условиям:

• После оставления только ребер из множества $C$ степень каждой вершины в $V$ равна $2$.
• После оставления только ребер из множества $C$ любые две вершины в $V$ являются связными.

Эта задача довольно проста! Сяо Ай написала динамическое программирование и решила её. Но затем она обнаружила шокирующую проблему: она не знает, как разделить число на $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$ — это сложение и умножение по модулю $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), то есть x ^ y в C++, а для умножения необходимо вызывать функцию 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$.