Walk

View as PDF

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

Problem types

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 with vertices, numbered .

For each and , you are given an integer that represents whether there is a directed edge from Vertex to . If , there is a directed edge from Vertex to ; if , there is not.

Find the number of different directed paths of length in , modulo . We will also count a path that traverses the same edge multiple times.

Constraints

• All values in input are integers.
• is or .

Input Specification

The first line will contain 2 space separated integers .

The next lines will each contain space separated integers, .

Output Specification

Print the number of different directed paths of length in , modulo .

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

is drawn in the figure below:

There are six directed paths of length :

Sample Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

Explanation For Sample 2

is drawn in the figure below:

There are three directed paths of length :

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

is drawn in the figure below:

There is one directed path of length :

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 .