Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

There is a simple directed graph G with N vertices, numbered 1, 2, \ldots, N.

For each i and j\ (1 \le i, j \le 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 \le N \le 50
  • 1 \le K \le 10^{18}
  • a_{i,j} is 0 or 1.
  • a_{i,i} = 0

Input Specification

The first line will contain 2 space separated integers N, K.

The next N lines will each contain N space separated integers, a_{i,j}.

Output Specification

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

Explanation For Sample 1

G is drawn in the figure below:

There are six directed paths of length 2:

  • 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 Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

Explanation For Sample 2

G is drawn in the figure below:

There are three directed paths of length 3:

  • 1 \rightarrow 2 \rightarrow 1 \rightarrow 2
  • 2 \rightarrow 1 \rightarrow 2 \rightarrow 1
  • 2 \rightarrow 1 \rightarrow 2 \rightarrow 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

Explanation For Sample 3

G is drawn in the figure below:

There is one directed path of length 2:

  • 4 \rightarrow 5 \rightarrow 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

Explanation For Sample 5

Be sure to print the count modulo 10^9+7.


Comments

There are no comments at the moment.