#P9522. [JOISC2022] 错误拼写

[JOISC2022] 错误拼写

题目背景

JOISC2022 D1T3

题目描述

从前,K 总统有着一个长度为 NN 的字符串 SS,仅由小写字母组成。然而,他忘记了它。
他还有一个词典,其中包含了各式各样的错误拼写。而他曾看过那本词典,现在他确认到 SS 满足以下条件:

  • TiT_i (1iN)(1\le i\le N)SS 删去第 ii 个字符并将前后字符相接所得的字符串。对于每个 jj (1jM)(1\le j\le M) 满足 TAjTBjT_{A_j} \le T_{B_j}

其中 TAjTBjT_{A_j} \le T_{B_j} 表示 TAjT_{A_j} 等于 TBjT_{B_j}TAjT_{A_j} 在字典序上小于 TBjT_{B_j}

请写一个程序,对于 K 总统给定的如上关于 SS 的信息,输出可能的 SS 的个数,对 109+710^9+7 取模。

输入格式

第一行,两个正整数 N,MN,M,表示 SS 的长度与限制的个数。

以下 MM 行,其中第 jj (1jM)(1 \le j \le M) 行包含两个正整数 Aj,BjA_j, B_j,表示一条限制。

输出格式

一行一个非负整数,表示可能的 SS 的个数对 109+710^9+7 取模的结果。

3 2
1 3
3 2
5876
5 6
1 2
1 5
2 4
5 4
5 3
4 3
656981
10 9
3 6
4 6
6 7
7 9
10 8
9 8
8 5
5 2
5 1
206289833

7 6
1 3
3 4
4 6
6 5
5 7
7 2
7125651
5 4
2 4
4 3
3 5
5 1
61451

提示

【样例解释 #1】

举例说明,若 S=babS=\texttt{bab},则 $T_1 = \texttt{ab}, T_2 = \texttt{bb}, T_3 = \texttt{ba}$。其满足 T1T3T_1 \le T_3T3T2T_3 \le T_2。所以该 SS 是合法的。
可以证明,总共有 58765876 种合法的 SS。因此,输出 58765876

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

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

【样例解释 #2】

该样例满足子任务 1,2,4,51,2,4,5 的限制。

【样例解释 #3】

取模前的结果为 824206295601824\,206\,295\,601,所以输出 206289833206\,289\,833

该样例满足子任务 1,2,4,51,2,4,5 的限制。

【样例解释 #4】

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

【样例解释 #5】

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

【数据范围】

对于所有数据,满足:

  • 2N5000002 \le N \le 500\,000
  • 1M5000001 \le M \le 500\,000
  • 1Aj,BjN1 \le A_j,B_j \le N (1jM)(1 \le j \le M)
  • AjBjA_j\ne B_j (1jM)(1 \le j \le M)
  • (Aj,Bj)(Ak,Bk)(A_j,B_j)\ne(A_k,B_k) (1j<kM)(1 \le j < k \le M)

详细子任务附加限制及分值如下表所示:

子任务编号 附加限制 分值
11 N10N \le 10 88
22 N200N \le 200 2020
33 存在 {1,2,,N}\{1,2,\dots,N\} 的排列 PP 满足 Aj=Pj,Bj=Pj+1A_j = P_j, B_j = P_{j+1} (1jM=N1)(1 \le j \le M=N-1) 2929
44 N20000N \le 20\,000 3232
55 无附加限制 1111