Counting Routes in a DAG

Difficulty: 1500 5000 ms 128 MB

dp graphs

Count the distinct directed paths from node 1 to node N in a DAG, modulo 10⁹+7.

Input: the first line has N and M; each of the next M lines has a directed edge u → v (the graph is acyclic).

Output: the number of 1 → N paths mod 10⁹+7.

Constraints:

• 2 ≤ N ≤ 10⁵
• 0 ≤ M ≤ 2×10⁵

Sample Tests

4 4
1 2
1 3
2 4
3 4

2

2 0

0

Read the Editorial