Xiao Ai chce policzyć, ile cykli Hamiltona znajduje się w grafie nieskierowanym.

Cykl Hamiltona $C$ to podzbiór zbioru krawędzi $C\subset E$ grafu $G=(V,E)$, który spełnia następujące warunki:

• Po pozostawieniu tylko krawędzi ze zbioru $C$, stopień każdego wierzchołka w $V$ wynosi $2$.
• Po pozostawieniu tylko krawędzi ze zbioru $C$, wszystkie wierzchołki w $V$ są połączone.

Ten problem jest dość prosty! Xiao Ai rozwiązała go za pomocą wymyślonego przez siebie DP. Jednak potem odkryła szokujący problem: nie wie, jak podzielić liczbę przez $2$!

Operacje

Możesz być zdziwiony, czyż dzielenie liczb naturalnych nie jest proste? W rzeczywistości liczby, którymi operuje Xiao Ai, nie są liczbami naturalnymi, które znamy. Wyjaśnijmy szczegółowo, jakie „operacje” może wykonywać Xiao Ai.

Xiao Ai potrafi szybko wykonywać obliczenia w zbiorze $R$, w którym zdefiniowano dodawanie i mnożenie. Dodawanie i mnożenie oznaczamy jako $\oplus$ oraz $\otimes$. Spełniają one znane nam prawa działań:

• Przemienność: dla dowolnych $x,y\in R$, zachodzi przemienność dodawania $x\oplus y = y\oplus x$ oraz przemienność mnożenia $x\otimes y = y\otimes x$.
• Łączność: dla dowolnych $x,y,z\in R$, zachodzi łączność dodawania $(x\oplus y)\oplus z= x\oplus(y\oplus z)$ oraz łączność mnożenia $(x\otimes y)\otimes z= x\otimes(y\otimes z)$.
• Rozdzielność: dla dowolnych $x,y,z\in R$, mnożenie jest rozdzielne względem dodawania $x\otimes (y\oplus z) = x\otimes y \oplus x\otimes z$.
• Element neutralny: istnieje unikalny element $0\in R$, taki że dla każdego $x\in R$ zachodzi $0\oplus x = x$, oraz unikalny element $1\in R$, taki że dla każdego $x\in R$ zachodzi $1\otimes x = x$.

Dlaczego Xiao Ai nie wie, jak dzielić przez dwa? Odkryliśmy, że podwojenie liczby powinno być tutaj zdefiniowane jako $x\oplus x$, ale w naszym zbiorze $R$ istnieje dodatkowe ograniczenie: dla każdego $x\in R$, $x\oplus x=0$. Zatem znając podwojoną wartość liczby, nie można z niej uzyskać żadnej informacji o liczbie wyjściowej.

Prosty przykład: niech $R=\{0,1\}$, a $\oplus, \otimes$ będą dodawaniem i mnożeniem modulo $2$. Wtedy $R$ spełnia wszystkie opisane powyżej właściwości.

Oznacza to, że w algorytmie Xiao Ai można nadal normalnie wykonywać dodawanie, mnożenie oraz dzielenie przez niezerową liczbę.

Problem

Sformułujmy problem ponownie.

Dany jest pełny graf nieskierowany $G$. Każda krawędź $e=(i,j), i < j$ ma wagę $w(e)\in R$. Waga cyklu Hamiltona $C$ jest zdefiniowana następująco: jeśli zbiór krawędzi to $\{e_1,e_2,\dots,e_n\}$, to waga wynosi $w(e_1)\otimes w(e_2)\otimes\cdots \otimes w(e_n)$. Szukaną odpowiedzią jest suma wag wszystkich cykli Hamiltona $C$, gdzie suma jest rozumiana jako operacja $\oplus$.

Szczegóły implementacji

W niniejszym zadaniu zbiór $R$ jest ciałem zwanym Nimber, a liczby są ograniczone do $32$-bitowych liczb całkowitych bez znaku. Dołączony plik sample.cpp zawiera szablon sprawdzający powyższe właściwości operacji. Po upewnieniu się, że wiesz, jak z niego korzystać, możesz usunąć kod sprawdzający i przystąpić do rozwiązania. Dodawanie $x,y$ to operacja XOR (w C++ x ^ y), a mnożenie wymaga wywołania funkcji nimbers::product(x, y) dostarczonej w bibliotece.

Gwarantujemy, że standardowe rozwiązanie tego zadania nie wykorzystuje żadnych szczególnych właściwości Nimberów w porównaniu do ogólnego zbioru $R$. Próba zrozumienia szczegółów implementacji szablonu lub właściwości Nimberów nie powinna przynieść żadnej dodatkowej pomocy w rozwiązaniu zadania.

Wejście

Pierwsza linia zawiera liczbę całkowitą dodatnią $n$, oznaczającą liczbę wierzchołków.

Następnie $n$ linii zawiera po $n$ $32$-bitowych liczb całkowitych bez znaku. Wartość w $i$-tym wierszu i $j$-tej kolumnie to $w(i,j)$, waga krawędzi $(i,j)$. Gwarantuje się, że $w(i,i)=0$ oraz $w(i,j)=w(j,i)$.

Wyjście

Wypisz $32$-bitową liczbę całkowitą bez znaku, oznaczającą odpowiedź.

Przykład

Przykład 1

Wejście:

3
0 1 1
1 0 1
1 1 0

Wyjście:

1

Przykład 2

Wejście:

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

Wyjście:

5

Przykład 3

Wejście:

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

Wyjście:

1269688359

Podzadania

Gwarantuje się, że $3\le n\le 20$.

Dla każdego testu $i(1\le i\le 5)$, gwarantuje się, że $n=i+2$.

Dla każdego testu $i(6\le i\le 10)$, gwarantuje się, że $n=i+10$.