给定一个 $N \times N$ 的方阵 $P(x)$，其中每个元素都是次数不超过 1 的多项式。 $P(x)$ 的第 $(i, j)$ 个元素为 $a_{i,j}x + b_{i,j}$。

计算乘积 $\prod_{i=0}^{M-1} P(2^ix) = P(x)P(2x) \dots P(2^{M-1}x)$ 的 $(1, 1)$ 位置元素 $f(x) = \sum_{i=0}^M c_ix^i$ 的各项系数 $c_0, c_1, \dots, c_M$，结果对 $(10^9 + 7)$ 取模。

本题的时间限制可能较为严格。

数据范围

• $1 \le N \le 6$
• $1 \le M \le 5 \times 10^5$
• $0 \le a_{i,j}, b_{i,j} < 10^9 + 7$

输入格式

输入通过标准输入按以下格式给出：

$N \ M$ $a_{1,1} \ a_{1,2} \dots \ a_{1,N}$ $a_{2,1} \ a_{2,2} \dots \ a_{2,N}$ $\vdots$ $a_{N,1} \ a_{N,2} \dots \ a_{N,N}$ $b_{1,1} \ b_{1,2} \dots \ b_{1,N}$ $b_{2,1} \ b_{2,2} \dots \ b_{2,N}$ $\vdots$ $b_{N,1} \ b_{N,2} \dots \ b_{N,N}$

输出格式

按顺序输出系数 $c_0, c_1, \dots, c_M$ 对 $(10^9 + 7)$ 取模的结果，每个系数占一行。

样例

输入 1

2 2
1 2
3 4
2 0
1 2

输出 1

4
8
14

说明

对于第一个样例：

由于 $$P(x)P(2x) = \begin{pmatrix} x + 2 & 2x \\ 3x + 1 & 4x + 2 \end{pmatrix} \begin{pmatrix} 2x + 2 & 4x \\ 6x + 1 & 8x + 2 \end{pmatrix} = \begin{pmatrix} 14x^2 + 8x + 4 & 20x^2 + 12x \\ 30x^2 + 24x + 4 & 44x^2 + 28x + 4 \end{pmatrix}$$

答案为 $f(x) = 14x^2 + 8x + 4$。