A data pipeline is a DAG with n stages 0 .. n-1 and directed links edges ([u, v] sends data from stage u to stage v). The graph is guaranteed to be acyclic and has no duplicate links.
Return the number of distinct routes from stage s to stage t (sequences of links starting at s and ending at t), taken modulo 10**9 + 7. The empty route counts when s == t.
Examples
Input: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [0, 3]], s = 0, t = 3
Output: 3
Explanation: 0-1-3, 0-2-3 and 0-3.
Input: n = 3, edges = [[0, 1]], s = 0, t = 2
Output: 0
Input: n = 2, edges = [[0, 1]], s = 1, t = 1
Output: 1
Constraints
1 <= n <= 10**4,0 <= len(edges) <= 3 * 10**4,0 <= s, t < n- Target: O(V + E) time.
Goals
- Count paths in a DAG with a forward DP over a topological order
- Apply a modulus at every addition to keep numbers small