You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1681 题。

题目描述

一个游戏有 $n$ 个关卡，通过 $m$ 个传送门连接。你的任务是从第 $1$ 关（起点）到第 $n$ 关（终点）。游戏的设计保证了在图中没有有向环路。你需要计算有多少种不同的方式可以完成这个游戏。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示关卡的数量和传送门的数量。关卡编号为 $1,2,…,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$。