Atcoder Educational DP Contest R - Walk

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho đồ thị có hướng ~G~ có ~N~ đỉnh, được đánh số từ ~1~ tới ~N~, dưới dạng ma trận kề ~a~ là một bảng gồm ~N~ hàng và ~N~ cột.

Với mỗi cặp số ~i~ và ~j~ ~(1 \le i,j \le N)~, số nguyên ~a_{i,j}~ thể hiện rằng có tồn tại hay không một cạnh có hướng từ đỉnh ~i~ tới đỉnh ~j~. Nếu ~a_{i,j} = 1~, thì tồn tại một cạnh có hướng từ đỉnh ~i~ tới đỉnh ~j~; còn nếu ~a_{i,j} = 0~ thì không tồn tại cạnh đó.

Hãy đếm số lượng đường đi khác nhau có độ dài ~K~ trong đồ thị ~G~, chia lấy số dư cho ~10^9 + 7~. Những con đường đi qua một cạnh nhiều lần cũng sẽ được tính.

Input

Dòng đầu tiên chứa hai số nguyên ~N\,(1 \le N \le 50)~ và ~K\,(1 \le K \le 10^{18})~.

~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên ~a_{i,j}\,(a_{i,j} \in \left \{ 0, 1 \right \}~, ~a_{i, i} = 0)~.

Output

In ra số lượng đường đi khác nhau có độ dài ~K~ trong đồ thị ~G~.

Sample 1

Input
4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0
Output
6
Giải thích

Đồ thị ~G~ trông như sau:

Có sáu đường đi có độ dài ~2~ là:

  • ~1 \rightarrow 2 \rightarrow 3~
  • ~1 \rightarrow 2 \rightarrow 4~
  • ~2 \rightarrow 3 \rightarrow 4~
  • ~2 \rightarrow 4 \rightarrow 1~
  • ~3 \rightarrow 4 \rightarrow 1~
  • ~4 \rightarrow 1 \rightarrow 2~

Sample 2

Input
3 3
0 1 0
1 0 1
0 0 0
Output
3
Giải thích

Đồ thị ~G~ trông như sau:

Có ba đường đi có độ dài ~3~ là:

  • ~1 \rightarrow 2 \rightarrow 1 \rightarrow 2~
  • ~2 \rightarrow 1 \rightarrow 2 \rightarrow 1~
  • ~2 \rightarrow 1 \rightarrow 2 \rightarrow 3~

Sample 3

Input
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
Output
1
Giải thích

Đồ thị ~G~ trông như sau:

Có đúng một đường đi có độ dài ~2~ là:

  • ~4 \rightarrow 5 \rightarrow 6~

Sample 4

Input
1 1
0
Output
0

Sample 5

Input
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
Output
957538352

Comments

Please read the guidelines before commenting.


There are no comments at the moment.