从前，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$ 取模的结果。

样例一

input

3 2
1 3
3 2

output

5876

explanation

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

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

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

样例二

input

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

output

656981

explanation

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

样例三

input

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

output

206289833

explanation

取模前的结果为 $824206295601$，所以输出 $206289833$。

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

样例四

input

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

output

7125651

explanation

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

样例五

input

5 4
2 4
4 3
3 5
5 1

output

61451

explanation

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

数据范围与提示

• $2\le N\le 500000$
• $1\le M\le 500000$
• $1\le A_i,B_i\le N(i\in [1,M])$
• $A_i\ne B_i(i\in [1,M])$
• $(A_i,B_i)\ne (A_j,B_j)(1\le i<j\le M)$

Subtasks

1. $\text{(8 points) }N\le 10$
2. $\text{(20 points) }N\le 200$
3. $\text{(29 points) }M=N-1$，并且存在长度为 $N$ 的排列 $P$ 使得 $A_j=P_j,B_j=P_{j+1}(j\in [1,M])$。
4. $\text{(32 points) }N\le 20000$
5. $\text{(11 points)}$ 无特殊限制。

时间限制：$\cancel{\mathtt{\text{3.5s}}}\mathtt{\text{4s}}$

空间限制：$\mathtt{\text{1GB}}$