{"problem":{"name":"[JOIST 2022] 错误拼写 / Misspelling","description":{"content":"从前，K 总统有着一个长度为 $N$ 的字符串 $S$，仅由小写字母组成。然而，他忘记了它。   他还有一个词典，其中包含了各式各样的错误拼写。而他曾看过那本词典，现在他确认到 $S$ 满足以下条件： - 令 $T_i$ $(1\\le i\\le N)$ 为 $S$ 删去第 $i$ 个字符并将前后字符相接所得的字符串。对于每个 $j$ $(1\\le j\\le M)$ 满足 $T_{A_j} \\le","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3500,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9522"},"statements":[{"statement_type":"Markdown","content":"从前，K 总统有着一个长度为 $N$ 的字符串 $S$，仅由小写字母组成。然而，他忘记了它。  \n他还有一个词典，其中包含了各式各样的错误拼写。而他曾看过那本词典，现在他确认到 $S$ 满足以下条件：\n\n- 令 $T_i$ $(1\\le i\\le N)$ 为 $S$ 删去第 $i$ 个字符并将前后字符相接所得的字符串。对于每个 $j$ $(1\\le j\\le M)$ 满足 $T_{A_j} \\le T_{B_j}$。\n\n其中 $T_{A_j} \\le T_{B_j}$ 表示 $T_{A_j}$ 等于 $T_{B_j}$ 或 $T_{A_j}$ 在字典序上小于 $T_{B_j}$。\n\n请写一个程序，对于 K 总统给定的如上关于 $S$ 的信息，输出可能的 $S$ 的个数，对 $10^9+7$ 取模。\n\n## Input\n\n第一行，两个正整数 $N,M$，表示 $S$ 的长度与限制的个数。\n\n以下 $M$ 行，其中第 $j$ $(1 \\le j \\le M)$ 行包含两个正整数 $A_j, B_j$，表示一条限制。\n\n## Output\n\n一行一个非负整数，表示可能的 $S$ 的个数对 $10^9+7$ 取模的结果。\n\n[samples]\n\n## Background\n\nJOISC2022 D1T3\n\n## Note\n\n**【样例解释 #1】**\n\n举例说明，若 $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$ 是合法的。  \n可以证明，总共有 $5876$ 种合法的 $S$。因此，输出 $5876$。\n\n另一方面，若 $S=\\texttt{aab}$，则 $T_1 = \\texttt{ab}, T_2 = \\texttt{ab}, T_3 = \\texttt{aa}$。其不满足 $T_1 \\le T_3$。所以该 $S$ 不合法。\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #2】**\n\n该样例满足子任务 $1,2,4,5$ 的限制。\n\n**【样例解释 #3】**\n\n取模前的结果为 $824\\,206\\,295\\,601$，所以输出 $206\\,289\\,833$。\n\n该样例满足子任务 $1,2,4,5$ 的限制。\n\n**【样例解释 #4】**\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #5】**\n\n该样例满足所有子任务的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $2 \\le N \\le 500\\,000$。  \n- $1 \\le M \\le 500\\,000$。\n- $1 \\le A_j,B_j \\le N$ $(1 \\le j \\le M)$。\n- $A_j\\ne B_j$ $(1 \\le j \\le M)$。\n- $(A_j,B_j)\\ne(A_k,B_k)$ $(1 \\le j < k \\le M)$。\n\n详细子任务附加限制及分值如下表所示：\n\n|子任务编号|附加限制|分值|\n|:-:|:-:|:-:|\n|$1$|$N \\le 10$|$8$|\n|$2$|$N \\le 200$|$20$|\n|$3$|存在 $\\{1,2,\\dots,N\\}$ 的排列 $P$ 满足 $A_j = P_j, B_j = P_{j+1}$ $(1 \\le j \\le M=N-1)$|$29$|\n|$4$|$N \\le 20\\,000$|$32$|\n|$5$|无附加限制|$11$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9522","tags":["2022","O2优化","JOISC/JOIST（日本）"],"sample_group":[["3 2\n1 3\n3 2","5876"],["5 6\n1 2\n1 5\n2 4\n5 4\n5 3\n4 3","656981"],["10 9\n3 6\n4 6\n6 7\n7 9\n10 8\n9 8\n8 5\n5 2\n5 1","206289833\n"],["7 6\n1 3\n3 4\n4 6\n6 5\n5 7\n7 2","7125651"],["5 4\n2 4\n4 3\n3 5\n5 1","61451"]],"created_at":"2026-03-03 11:09:25"}}