题目描述

题目译自 JOISC 2022 Day1 T3「スペルミス / Misspelling」。

从前，K 总统有一个长度为 $N$ 的字符串 $S$，仅由小写字母组成。然而，他忘记了它。
他还有一个词典，其中包含了各式各样的错误拼写。他曾经看过那本词典，现在他确认 $S$ 满足以下条件：

令 $T_i$（$1 \le i \le N$）为 $S$ 删去第 $i$ 个字符并将前后字符相接所得的字符串。
对于每个 $j$（$1 \le j \le M$），满足 $T_{A_j} \le T_{B_j}$。
其中 $T_{A_j} \le T_{B_j}$ 表示 $T_{A_j}$ 等于 $T_{B_j}$ 或 $T_{A_j}$ 在字典序上小于 $T_{B_j}$。

请写一个程序，对于 K 总统给定的如上关于 $S$ 的信息，输出可能的 $S$ 的个数，对 $10^9+7$ 取模。

---

输入格式

第一行，两个正整数 $N, M$，表示 $S$ 的长度与限制的个数。
以下 $M$ 行，其中第 $j$（$1 \le j \le M$）行包含两个正整数 $A_j, B_j$，表示一条限制。

---

输出格式

一行一个非负整数，表示可能的 $S$ 的个数对 $10^9+7$ 取模的结果。

---

样例 1

输入

3 2
1 3
3 2

输出

5876

举例说明， 若 $S = \texttt{bab}$，则 $T_1 = \texttt{ab}$，$T_2 = \texttt{bb}$，$T_3 = \texttt{ba}$。
满足 $T_1 \le T_3$ 和 $T_3 \le T_2$，所以该 $S$ 是合法的。
可以证明，总共有 $5876$ 种合法的 $S$，因此输出 $5876$。

另一方面，若 $S = \texttt{aab}$，则 $T_1 = \texttt{ab}$，$T_2 = \texttt{ab}$， $T_3 = \texttt{aa}$。
不满足 $T_1 \le T_3$，所以该 $S$ 不合法。

该样例满足所有子任务的限制。

---

样例 2

输入

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

输出

656981

该样例满足子任务 $1,2,4,5$ 的限制。

---

样例 3

输入

10 9
3 6
4 6
6 7
7 9
10 8
9 8
8 5
5 2
5 1

输出

206289833

取模前的结果为 $824\,206\,295\,601$，所以输出 $206\,289\,833$。

该样例满足子任务 $1,2,4,5$ 的限制。

---

样例 4

输入

7 6
1 3
3 4
4 6
6 5
5 7
7 2

输出

7125651

该样例满足所有子任务的限制。

---

样例 5

输入

5 4
2 4
4 3
3 5
5 1

输出

61451

该样例满足所有子任务的限制。

---

数据范围与提示

对于所有数据，满足：

• $2 \le N \le 500\,000$
• $1 \le M \le 500\,000$
• $1 \le A_j, B_j \le N$（$1 \le j \le M$）
• $A_j \ne B_j$（$1 \le j \le M$）
• $(A_j,B_j) \ne (A_k,B_k)$（$1 \le j < k \le M$）

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
1	$N \le 10$	8
2	$N \le 200$	20
3	存在 $\{1,2,\dots,N\}$ 的排列 $P$ 满足 $A_j = P_j, B_j = P_{j+1}$（$1 \le j \le M=N-1$）	29
4	$N \le 20\,000$	32
5	无附加限制	11