Count Paths in a DAG

Silver

10000ms500MB

You are given a directed acyclic graph with n nodes labeled 1 to n, described by an array edges, where edges[i] = [a, b] is a one-way edge from a to b. Multiple edges may connect the same pair of nodes, and each one counts as a distinct way to move.

Count the distinct paths from node 1 to node n.

Return the count modulo 10^9 + 7.

Examples

Example 1

Input: n = 4, edges = [[1,2],[2,4],[1,3],[3,4],[1,4]]
Output: 3
Explanation: The paths are 1 -> 2 -> 4, 1 -> 3 -> 4 and 1 -> 4.

Example 2

Input: n = 3, edges = [[1,2]]
Output: 0
Explanation: Node 3 is unreachable from node 1.

Constraints

$1 \leq n \leq 10^5$
$0 \leq$ edges.length $\leq 2 \cdot 10^5$
edges[i].length $= 2$
$1 \leq a, b \leq n$
The graph contains no directed cycles.

Examples

Example 1

Input

n = 4

edges = [[1, 2], [2, 4], [1, 3], [3, 4], [1, 4]]

Output

Example 2

Input

n = 3

edges = [[1, 2]]

Output

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.

Count Paths in a DAG

Silver

10000ms500MB

Count the distinct paths from node 1 to node n.

Return the count modulo 10^9 + 7.

Examples

Example 1

Input: n = 4, edges = [[1,2],[2,4],[1,3],[3,4],[1,4]]
Output: 3
Explanation: The paths are 1 -> 2 -> 4, 1 -> 3 -> 4 and 1 -> 4.

Example 2

Input: n = 3, edges = [[1,2]]
Output: 0
Explanation: Node 3 is unreachable from node 1.

Constraints

$1 \leq n \leq 10^5$
$0 \leq$ edges.length $\leq 2 \cdot 10^5$
edges[i].length $= 2$
$1 \leq a, b \leq n$
The graph contains no directed cycles.

Examples

Example 1

Input

n = 4

edges = [[1, 2], [2, 4], [1, 3], [3, 4], [1, 4]]

Output

Example 2

Input

n = 3

edges = [[1, 2]]

Output

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.