Problem Description

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

Now Xiao A is going to take several trips on the graph. In each trip, he chooses any starting point, walks at least one step, and ends at any destination point. Define the enjoyment value of a trip as the bitwise AND of the indices of the starting point and the ending point.

Curious Xiao B wants to know: for all $x \in [1,m]$ and $y \in [0,n)$, the number of ways such that Xiao A takes several trips, walks a total of $x$ steps, and the bitwise AND of the enjoyment values of all trips equals $y$.

Two ways are different if and only if the number of trips is different, or some trip is not exactly the same.

To avoid outputting too much, you only need to output the bitwise XOR of these $n \times m$ numbers after taking them modulo $998244353$.

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

Input Format

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

Then follows an $n \times n$ matrix. The number in row $i$ and column $j$ represents the number of directed edges from vertex $i-1$ to vertex $j-1$.

Output Format

Output one integer, representing the bitwise XOR value of the $n \times m$ answers after taking them modulo $998244353$.

2 3
1 2
3 4

1770

Hint

Sample Explanation

For walking $1$ step, the numbers of ways with enjoyment-value bitwise AND $= 0,1$ are $6,4$, respectively.

For walking $2$ steps, they are $116,38$, respectively.

For walking $3$ steps, they are $2012,358$, respectively.

The XOR value is $1770$.

Constraints

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

Translated by ChatGPT 5