很久以前，K 总统有一个长度为 $N$ 的由小写字母组成的字符串 $S$。但他忘记了这个字符串。 他有一个包含多种拼写错误的字典，他曾查阅过字典以检查字符串 $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$ 满足这些信息，结果对 $1\,000\,000\,007$ 取模。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N \ M$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$

输出格式

输出一行到标准输出。输出应包含满足给定信息的字符串 $S$ 的数量，结果对 $1\,000\,000\,007$ 取模。

数据范围

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

子任务

1. (8 分) $N \le 10$
2. (20 分) $N \le 200$
3. (29 分) $M = N - 1$。此外，存在一个长度为 $N$ 的排列 $P$ 的 $(1, 2, \dots, N)$ 满足 $A_j = P_j$ 且 $B_j = P_{j+1}$ ($1 \le j \le M$)。
4. (32 分) $N \le 20\,000$
5. (11 分) 无附加限制。

样例

样例输入 1

3 2
1 3
3 2

样例输出 1

5876

说明

例如，如果字符串 $S$ 为 bab，我们有 $T_1 = \text{ab}$，$T_2 = \text{bb}$，$T_3 = \text{ba}$。关系 $T_1 \le T_3$ 和 $T_3 \le T_2$ 成立。该字符串不与给定信息矛盾。总共有 5876 个字符串 $S$ 不与给定信息矛盾。因此，输出 5876。

另一方面，例如，如果字符串 $S$ 为 aab，我们有 $T_1 = \text{ab}$，$T_2 = \text{ab}$，$T_3 = \text{aa}$。关系 $T_1 \le T_3$ 不成立。因此，该字符串与给定信息矛盾。

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

样例输入 2

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

样例输出 2

656981

样例输入 3

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

样例输出 3

206289833

样例输入 4

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

样例输出 4

7125651

样例输入 5

5 4
2 4
4 3
3 5
5 1

样例输出 5

61451