题目描述

给定一个有向图，这个图有 $n$ 个点，点从 $1$ 到 $n$ 进行编号，并给定一个邻接矩阵 $a_{i,j}$：

• 若 $a_{i,j}=1$ 表示点 $i$ 到点 $j$ 存在一条边；
• 若 $a_{i,j}=0$ 表示点 $i$ 到点 $j$ 不存在一条边。

给定一个整数 $k$，请计算在图上从 $1$ 号点出发，到 $n$ 号点结束，有多少条长度恰好为 $k$ 的路径。由于方案数很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

• 第一行：两个整数表示 $n$ 与 $k$
• 第二行到第 $n+1$ 行：第 $i+1$ 行有 $n$ 个整数表示 $a_{i,1},a_{i,2},\dots,a_{i,n}$

输出格式

• 单个整数：表示答案。

3 2
0 1 1
1 0 1
1 1 0

1

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 16$，$1\leq k\leq 100$
• 对于 $60\%$ 的数据，$1\leq n\leq 32$，$1\leq k\leq 10000$
• 对于 $100\%$ 的数据，$1\leq n\leq 64$，$1\leq k\leq 10^{18}$