7579: [CSES Problem Set] Game Routes
[Creator : ]
Description
A game has $n$ levels, connected by mm teleporters, and your task is to get from level $1$ to level $n$. The game has been designed so that there are no directed cycles in the underlying graph. In how many ways can you complete the game?
Input
The first input line has two integers $n$ and $m$: the number of levels and teleporters. The levels are numbered $1,2,\dots,n$.
After this, there are mm lines describing the teleporters. Each line has two integers $a$ and $b$: there is a teleporter from level $a$ to level $b$.
After this, there are mm lines describing the teleporters. Each line has two integers $a$ and $b$: there is a teleporter from level $a$ to level $b$.
Output
Print one integer: the number of ways you can complete the game. Since the result may be large, print it modulo $10^9+7$.
Constraints
$1≤n≤10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
Sample 1 Input
4 5
1 2
2 4
1 3
3 4
1 4
Sample 1 Output
3