题目描述
K 总统忘记了一个只含小写字母、长度为 N 的字符串 S。删除 S 的第 i 个字符并连接前后部分,得到字符串 Ti。给出 M 条限制,要求对每条限制 TAj≤TBj,其中不等号表示字典序不大于。请统计可能的 S 数量,答案对 109+7 取模。
输入格式
从 typo.in 文件读入数据。
第一行包含 N,M。接下来 M 行,每行包含 Aj,Bj,表示限制 TAj≤TBj。
输出格式
输出到 typo.out 文件。
输出可能的字符串 S 数量对 109+7 的余数。
样例 1 输入
3 2
1 3
3 2
样例 1 输出
5876
样例 2 输入
5 6
1 2
1 5
2 4
5 4
5 3
4 3
样例 2 输出
656981
数据范围
满足 2≤N≤500000,1≤M≤500000,1≤Aj,Bj≤N,Aj=Bj,并且限制对 (Aj,Bj) 两两不同。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 |
分值 |
测试点 |
附加条件 |
| 1 |
8 |
1∼3 |
N≤10 |
| 2 |
20 |
4∼7 |
N≤200 |
| 3 |
29 |
8∼12 |
存在排列 P,使 M=N−1 且对每个 j 有 Aj=Pj,Bj=Pj+1 |
| 4 |
32 |
13∼17 |
N≤20000 |
| 5 |
11 |
18∼20 |
无额外限制 |