Little A has a graph with $n$ vertices, labeled from $0$ to $n-1$. There are $A_{i,j}$ directed edges from vertex $i$ to vertex $j$. Self-loops may exist.

Little A wants to perform several trips on the graph. Each trip consists of choosing an arbitrary starting vertex, traversing at least one edge, and ending at an arbitrary vertex. The "pleasure value" of a trip is defined as the bitwise AND of the starting vertex index and the ending vertex index.

Curious Little B wants to know: for all $x \in [1, m]$ and $y \in [0, n)$, what is the number of ways for Little A to perform several trips such that the total number of steps taken is $x$, and the bitwise AND of the pleasure values of all trips is $y$?

Two schemes are considered different if and only if the number of trips is different or at least one trip is not identical.

To avoid excessive output, you only need to output the bitwise XOR sum of these $n \times m$ values modulo $998244353$.

For convenience, it is guaranteed that $n$ is a power of $2$.

Input

The first line contains two integers $n$ and $m$.

The following is an $n \times n$ matrix, where the number in the $i$-th row and $j$-th column represents the number of directed edges from vertex $i-1$ to vertex $j-1$.

Output

Output a single integer representing the XOR sum of the $n \times m$ answers modulo $998244353$.

Examples

Input 1

2 3
1 2
3 4

Output 1

1770

Note

For $1$ step, the number of ways with pleasure value bitwise AND equal to $0$ and $1$ are $6$ and $4$, respectively.

The number of ways for $2$ steps are $116$ and $38$, respectively.

The number of ways for $3$ steps are $2012$ and $358$, respectively.

The XOR sum is $1770$.

Subtasks

For all data, $2 \leq n \leq 64, 1 \leq m \leq 20000, 0 \leq A_{i,j} < 998244353$, and $n$ is a power of $2$.