Xiao Ai wants to count the number of Hamiltonian cycles in an undirected graph.

A Hamiltonian cycle $C$ is a subset of edges $C \subset E$ of a graph $G=(V, E)$ that satisfies the following conditions:

• After keeping only the edges in $C$, the degree of every vertex in $V$ is exactly $2$.
• After keeping only the edges in $C$, any two vertices in $V$ are connected.

This problem is quite simple! Xiao Ai solved it using a random DP. However, she then discovered a shocking problem: she doesn't know how to divide a number by $2$!

Operations

You might be confused; isn't division of natural numbers simple? In fact, the numbers Xiao Ai is dealing with are not the natural numbers we are familiar with. We will explain in detail what kind of "operations" Xiao Ai can perform.

Xiao Ai can perform calculations quickly on a set $R$ where addition and multiplication are defined. We call the addition and multiplication $\oplus$ and $\otimes$, respectively. They satisfy the operational laws we are familiar with:

• Commutativity: For any $x, y \in R$, addition is commutative $x \oplus y = y \oplus x$ and multiplication is commutative $x \otimes y = y \otimes x$.
• Associativity: For any $x, y, z \in R$, addition is associative $(x \oplus y) \oplus z = x \oplus (y \oplus z)$ and multiplication is associative $(x \otimes y) \otimes z = x \otimes (y \otimes z)$.
• Distributivity: For any $x, y, z \in R$, multiplication distributes over addition $x \otimes (y \oplus z) = x \otimes y \oplus x \otimes z$.
• Identity elements: There exists a unique element $0 \in R$ such that for any $x \in R$, $0 \oplus x = x$, and a unique element $1 \in R$ such that for any $x \in R$, $1 \otimes x = x$.

Why doesn't Xiao Ai know how to divide by two? We find that the appropriate definition of "twice a number" here should be $x \oplus x$, but here, our $R$ has an additional constraint: for any $x \in R$, $x \oplus x = 0$. Therefore, knowing twice a number provides no information about the original number.

A simple example: Let $R = \{0, 1\}$, and define $\oplus, \otimes$ as addition and multiplication modulo $2$. Then $R$ satisfies all the properties we just described.

This means that in Xiao Ai's algorithm, addition, multiplication, and division by a non-zero number can still be performed normally.

Problem

Now let us restate the original problem.

Given a complete undirected graph $G$, define the weight of each edge $e = (i, j), i < j$ as $w(e) \in R$. We define the weight of a Hamiltonian cycle $C$ as follows: let the edge set be $\{e_1, e_2, \dots, e_n\}$, the weight is the product of the edge weights $w(e_1) \otimes w(e_2) \otimes \cdots \otimes w(e_n)$. The answer we seek is the sum of the weights of all Hamiltonian cycles $C$, where the sum is the $\oplus$ sum.

Implementation

In the implementation of this problem, the $R$ we have chosen is a field called Nimber, and the numbers are limited to $32$-bit unsigned integers. The provided sample.cpp includes a template that verifies the above operational properties. You can delete the verification code after confirming you understand how to use it. The addition of $x, y$ is the XOR operation, i.e., x ^ y in C++, and multiplication requires calling the function nimbers::product(x, y) provided in the library.

We guarantee that the standard solution to this problem does not use any special properties of Nimbers compared to a general $R$. Attempting to understand the implementation details of the template or the properties of Nimbers should not be of any additional help in solving this problem.

Input

The first line contains a positive integer $n$, representing the number of nodes.

The next $n$ lines each contain $n$ $32$-bit unsigned integers. The $j$-th column of the $i$-th row is $w(i, j)$, representing the weight of edge $(i, j)$. It is guaranteed that $w(i, i) = 0$ and $w(i, j) = w(j, i)$.

Output

Output a $32$-bit unsigned integer representing the answer.

Examples

Input 1

3
0 1 1
1 0 1
1 1 0

Output 1

1

Input 2

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

Output 2

5

Input 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

Output 3

1269688359

Subtasks

It is guaranteed that $3 \le n \le 20$.

For the $i$-th ($1 \le i \le 5$) test case, it is guaranteed that $n = i + 2$.

For the $i$-th ($6 \le i \le 10$) test case, it is guaranteed that $n = i + 10$.