Walks of Astronomical Length

Difficulty: 1800 6000 ms 128 MB

graphs matrix-exponentiation

Count the directed walks of EXACTLY K edges from node 1 to node N, modulo 10⁹+7. K is up to 10¹⁸.

Input: the first line has N, M and K; each of the next M lines has a directed edge u v (multi-edges allowed and counted).

Output: the number of length-K walks mod 10⁹+7.

Constraints:

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 10⁴
• 1 ≤ K ≤ 10¹⁸

Sample Tests

3 3 2
1 2
2 3
1 3

1

2 1 1
1 2

1

Read the Editorial