Game Routes

题目描述

一个游戏有 n 个关卡，由 m 个传送门连接，任务是从关卡 1 到达关卡 n。题目保证在底层有向图中不存在有向环。共有多少种完成游戏的方式？

输入格式

第一行包含两个整数 n 和 m：关卡数和传送门数。关卡编号为 1,2,$\dots$,n。 接下来有 m 行描述传送门。每行有两个整数 a 和 b：表示存在一条从关卡 a 到关卡 b 的传送门。

输出格式

输出一个整数：可以完成游戏的方案数。由于结果可能很大，请对 $10^9+7$ 取模后输出。

4 5
1 2
2 4
1 3
3 4
1 4

3

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1681|图论

来源

CSES1681|图论