Description

有一个具有 $N$ 个顶点的简单有向图 $G$，编号为 $1,2,…,N$。

对于每个 $i$ 和 $j(1≤i,j≤N)$ ，给你一个整数 $a_{i,j}$，它表示是否存在从顶点 $i$ 到 $j$ 的有向边；如果 $a_{i,j}=1$，表示有；如果 $a_{i,j}​=0$，表示没有。

求 $G$ 中长度为 $K$ 的不同有向路径的数量，模 $10^9+7$。允许多次经过同一条有向边。

Input

输入格式如下：

$N\ K\\a_{1,1} … a_{1,N}\\​:\\a_{N,1} … a_{N,N}$

输入中的所有值都是整数。

$1≤N≤50\\1≤K≤10^{18}\\a_{i,j}= 0 or 1\\a_{i,i}=0$

Output

输出 $G$ 中长度为 $K$ 的不同有向路径的数量，模 $10^9+7$

Samples

4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0

6

$G$ 如下图所示：

有六条长度为2的有向路径：

$1 → 2 → 3\\1 → 2 → 4\\2 → 3 → 4\\2 → 4 → 1\\3 → 4 → 1\\4 → 1 → 2$

3 3
0 1 0
1 0 1
0 0 0

3

$G$ 如下图所示：

有三条长度为3的有向路径：

$1 → 2 → 1 → 2\\2 → 1 → 2 → 1\\2 → 1 → 2 → 3$

6 2
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0

1

$G$ 如下图所示：

有一条长度为2的有向路径：

$4 → 5 → 6$

1 1
0

0

10 1000000000000000000
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 0 1 1 0
0 1 1 1 0 1 0 1 1 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 0

957538352

务必输出模 $10^9+7$ 的结果。