294. Paths in a DAG
MediumTopological SortDP
Count the paths from node 1 to node n in the directed acyclic graph. Print modulo 10⁹ + 7.
Input format
Line 1: n m Next m lines: u v (edge u → v)
Output format
The number of paths mod 10⁹ + 7.
Example 1
Input
4 5 1 2 1 3 2 4 3 4 2 3
Output
3
Example 2
Input
3 1 1 2
Output
0
Constraints
2 ≤ n ≤ 10⁵
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…