题目背景

你知道矩阵乘法吗？

对于两个 $n\times n$ 的矩阵 A 和 B， 假设 $a_{i, j}$ 表示位于矩阵 A 的第 $i$ 行第 $j$ 列的元素， 同样对于B可以定义类似的 $b_{i,j}$。 那么如果 $C = A \times B$，则有 $c_{i, j}=\sum_{k=1}^{n} a_{ik} \times b_{kj}$。 其中 $\sum$ 是序列求和符号，例如 $\sum_{i=1}^{n} i$ 表示 $1 + 2 + \cdots + n$。

题目描述

由于霍比特人的大热， L 的室友 X 最近热衷于研究它们所使用的货币。为了进行研究，X 需要了解一种叫比特矩阵的东西。 虽然比特矩阵也是矩阵，但是它的乘法和一般的矩阵有点不一样。

对于比特矩阵 $C = A \times B$， 意味着 $c_{i,j} = V_{k=1}^{n}a_{ik} \bigoplus b_{kj}$。其中 $V$ 是序列求按位或的符号，例如 $V_{i=1}^{n} i$ 表示 $1 \mid 2 \mid \cdots \mid n$。 $\mid$ 就是按位或的意思。 按位或是指从二进制的角度看两个数， 如果第 $i$ 位上两个数至少一个是1的话那结果的第 $i$ 位就是1， 否则第 $i$ 位就是 $0$。 $\bigoplus$ 表示按位异或运算， 即如果两个二进制数的第$i$位是不相同的话那么结果的第 $i$ 位就是 $1$，否则就是 $0$。

举个比特矩阵相乘的例子:

$$\begin{bmatrix}1&6\\3&5\end{bmatrix}\times\begin{bmatrix}3&6\\5&7\end{bmatrix}=\begin{bmatrix}3&7\\0&7\end{bmatrix} $$

现在 X 想要拜托你帮他算 $A^{m}$，其中 $A$ 是一个 $n\times n$ 的比特矩阵， 而 $A^{m}$ 表示 $m$ 个 $A$ 相乘的结果。严谨地说:

• $A^{1}=A$；
• $A^{m}=A^{m-1}\times A,\ m>1$。

输入格式

输入第一行包含两个正整数 $n,m$。

接下来 $n$ 行，每行包含 $n$ 个非负整数，这 $n$ 行中第 $i$ 行的第 $j$ 个数表示比特矩阵 $a_{i,j}$ 的元素 。

输出格式

根据输入，输出一个比特矩阵 $A^{m}$。即按照输入给出 $A$ 的方式输出一个比特矩阵。 具体参看样例输出。

2 4
10 5
5 10

0 15
15 0

3 16
6 5 7
5 6 7
7 7 6

0 3 3
3 0 3
3 3 0

提示

数据范围及约定

• 对于 $10\%$ 的数据 $n\le 4$，$m\le 10000$。
• 对于 $30\%$ 的数据 $n\le 10$，$m\le 10^9$。
• 对于 $100\%$ 的数据 $n\le 500$，$m\le 10^9$, 所有输入的整数不超过$10^9$。