#CW56. 打字错误(typo)

打字错误(typo)

题目描述

K 总统忘记了一个只含小写字母、长度为 NN 的字符串 SS。删除 SS 的第 ii 个字符并连接前后部分,得到字符串 TiT_i。给出 MM 条限制,要求对每条限制 TAj≤TBjT_{A_j} \le T_{B_j},其中不等号表示字典序不大于。请统计可能的 SS 数量,答案对 109+710^9+7 取模。

输入格式

从 typo.in 文件读入数据。

第一行包含 N,MN, M。接下来 MM 行,每行包含 Aj,BjA_j, B_j,表示限制 TAj≤TBjT_{A_j} \le T_{B_j}。

输出格式

输出到 typo.out 文件。

输出可能的字符串 SS 数量对 109+710^9+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≤5000002 \le N \le 500000,1≤M≤5000001 \le M \le 500000,1≤Aj,Bj≤N1 \le A_j, B_j \le N,Aj≠BjA_j \ne B_j,并且限制对 (Aj,Bj)(A_j, B_j) 两两不同。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 8 1∼31\sim 3 N≤10N \le 10
2 20 4∼74\sim 7 N≤200N \le 200
3 29 8∼128\sim 12 存在排列 PP,使 M=N−1M=N-1 且对每个 jj 有 Aj=PjA_j=P_j,Bj=Pj+1B_j=P_{j+1}
4 32 13∼1713\sim 17 N≤20000N \le 20000
5 11 18∼2018\sim 20 无额外限制