题目描述

给定一个有 $N$ 个点的简单有向图，点的编号为 $1\sim N$。

对于每一对点 $(i,j)$，给出一个整数 $a_{i,j}$：

• 若 $a_{i,j}=1$，表示图中存在一条从点 $i$ 指向点 $j$ 的有向边；
• 若 $a_{i,j}=0$，表示这条有向边不存在。

请你求出：这张图中长度恰好为 $K$ 的有向路径一共有多少条，答案对 $10^9+7$ 取模。

注意：

• 这里的“长度为 $K$”指路径恰好经过 $K$ 条边；
• 允许一条路径中重复经过同一条边；
• 图是简单有向图，因此不存在自环，即 $a_{i,i}=0$。

输入格式

第一行两个整数 $N,K$。
接下来 $N$ 行，每行 $N$ 个整数，第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。

• $1\le N\le 50$
• $1\le K\le 10^{18}$
• $a_{i,j}\in\{0,1\}$
• $a_{i,i}=0$

输出格式

输出一个整数，表示长度恰好为 $K$ 的有向路径总数，对 $10^9+7$ 取模后的结果。

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

6

Hint

样例解释： 长度为 $2$ 的有向路径共有 6 条：

• $1\to 2\to 3$
• $1\to 2\to 4$
• $2\to 3\to 4$
• $2\to 4\to 1$
• $3\to 4\to 1$
• $4\to 1\to 2$