/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
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 で割った余りを求めてください。 ただし、同じ辺を複数回通るような有向パスも数えるものとします。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 50
- 1 \leq K \leq 10^{18}
- a_{i, j} は 0 または 1 である。
- a_{i, i} = 0
入力
入力は以下の形式で標準入力から与えられる。
N K
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}
出力
G の長さ K の有向パスは何通りか？ 10^9 + 7 で割った余りを出力せよ。
入力例 1
4 2 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0
出力例 1
6
G は次図です。
長さ 2 の有向パスは、次の 6 通りです。
- 1 → 2 → 3
- 1 → 2 → 4
- 2 → 3 → 4
- 2 → 4 → 1
- 3 → 4 → 1
- 4 → 1 → 2
入力例 2
3 3 0 1 0 1 0 1 0 0 0
出力例 2
3
G は次図です。
長さ 3 の有向パスは、次の 3 通りです。
- 1 → 2 → 1 → 2
- 2 → 1 → 2 → 1
- 2 → 1 → 2 → 3
入力例 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
出力例 3
1
G は次図です。
長さ 2 の有向パスは、次の 1 通りです。
- 4 → 5 → 6
入力例 4
1 1 0
出力例 4
0
入力例 5
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
出力例 5
957538352
答えを 10^9 + 7 で割った余りを出力することを忘れずに。
Score : 100 points
Problem Statement
There is a simple directed graph G with N vertices, numbered 1, 2, \ldots, N.
For each i and j (1 \leq i, j \leq N), you are given an integer a_{i, j} that represents whether there is a directed edge from Vertex i to j. If a_{i, j} = 1, there is a directed edge from Vertex i to j; if a_{i, j} = 0, there is not.
Find the number of different directed paths of length K in G, modulo 10^9 + 7. We will also count a path that traverses the same edge multiple times.
Constraints
- All values in input are integers.
- 1 \leq N \leq 50
- 1 \leq K \leq 10^{18}
- a_{i, j} is 0 or 1.
- a_{i, i} = 0
Input
Input is given from Standard Input in the following format:
N K
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}
Output
Print the number of different directed paths of length K in G, modulo 10^9 + 7.
Sample Input 1
4 2 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0
Sample Output 1
6
G is drawn in the figure below:
There are six directed paths of length 2:
- 1 → 2 → 3
- 1 → 2 → 4
- 2 → 3 → 4
- 2 → 4 → 1
- 3 → 4 → 1
- 4 → 1 → 2
Sample Input 2
3 3 0 1 0 1 0 1 0 0 0
Sample Output 2
3
G is drawn in the figure below:
There are three directed paths of length 3:
- 1 → 2 → 1 → 2
- 2 → 1 → 2 → 1
- 2 → 1 → 2 → 3
Sample Input 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
Sample Output 3
1
G is drawn in the figure below:
There is one directed path of length 2:
- 4 → 5 → 6
Sample Input 4
1 1 0
Sample Output 4
0
Sample Input 5
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
Sample Output 5
957538352
Be sure to print the count modulo 10^9 + 7.