P9522 [JOIST 2022] 错误拼写 / Misspelling

JOISC2022 D1T3

从前，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】** 举例说明，若 $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】** 该样例满足子任务 $1,2,4,5$ 的限制。 **【样例解释 #3】** 取模前的结果为 $824\,206\,295\,601$，所以输出 $206\,289\,833$。 该样例满足子任务 $1,2,4,5$ 的限制。 **【样例解释 #4】** 该样例满足所有子任务的限制。 **【样例解释 #5】** 该样例满足所有子任务的限制。 **【数据范围】** 对于所有数据，满足： - $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$|