AT_dp_r Walk

给定一个有 $N$ 个顶点的简单有向图 $G$。顶点编号为 $1, 2, \ldots, N$。 对于每一对 $i, j$（$1 \leq i, j \leq N$），是否存在从顶点 $i$ 到顶点 $j$ 的有向边由整数 $a_{i, j}$ 给出。若 $a_{i, j} = 1$，则表示存在从 $i$ 到 $j$ 的有向边；若 $a_{i, j} = 0$，则不存在。 请问在图 $G$ 中，长度为 $K$ 的有向路径共有多少条？请输出答案对 $10^9 + 7$ 取模的结果。注意，可以多次经过同一条边的路径也要计入。

输入通过标准输入给出，格式如下： > $N$ $K$ $a_{1,1}$ $\ldots$ $a_{1,N}$ $:$ $a_{N,1}$ $\ldots$ $a_{N,N}$

请输出图 $G$ 中长度为 $K$ 的有向路径的总数，对 $10^9 + 7$ 取模。

## 限制条件 - 所有输入均为整数。 - $1 \leq N \leq 50$ - $1 \leq K \leq 10^{18}$ - $a_{i, j}$ 仅为 $0$ 或 $1$。 - $a_{i, i} = 0$ ## 样例解释 1 图 $G$ 如下所示。  长度为 $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$ ## 样例解释 2 图 $G$ 如下所示。  长度为 $3$ 的有向路径共有如下 $3$ 条： - $1 \to 2 \to 1 \to 2$ - $2 \to 1 \to 2 \to 1$ - $2 \to 1 \to 2 \to 3$ ## 样例解释 3 图 $G$ 如下所示。  长度为 $2$ 的有向路径共有如下 $1$ 条： - $4 \to 5 \to 6$ ## 样例解释 5 请不要忘记将答案对 $10^9 + 7$ 取模。 由 ChatGPT 4.1 翻译