AT_joisc2022_c.スペルミス (Misspelling)

官方文档

有一个长为 $n$ 的小写英文字母串 $s$。给出 $m$ 条信息。记 $t_i$ 为 $s$ 在删去第 $i$ 个字符后的字符串，则第 $j$ 条信息形如“$t_{a_j}$ 的字典序不大于 $t_{b_j}$ 的字典序”。

请求出满足要求的 $s$ 的个数对 $(10^9+7)$ 取模的结果。

第一行为两个整数 $n$ 和 $m$，中间以单个空格隔开。

接下来 $m$ 行，第 $i$ 行为两个整数 $a_i$ 和 $b_i$，表示 $t_{a_i}$ 的字典序不大于 $t_{b_i}$ 的字典序。

一行一个整数，题目所求。

样例请至官方文档查看。

数据规模与约定

对于 $100\%$ 的测试点，数据保证：

• $2\le n\le 5\times 10^5$；
• $1\le m\le 5\times 10^5$；
• 对于任意 $1\le j\le m$ 的整数 $j$，都有 $1\le a_j\le n$，$1\le b_j\le n$，$a_j\neq b_j$；
• 对于任意整数对 $(j,k)$ 满足 $1\le j\lt k\le m$，都有 $(a_j,b_j)\neq(a_k,b_k)$。

本题设有部分分。

子任务分值及特殊性质如下：

子任务编号	分值	特殊性质
$1$	$8$	$n\le 10$
$2$	$20$	$n\le 200$
$3$	$29$	$m=n-1$，且对于某个由 $(1,2,...,n)$ 重排而成的序列 $p$，有 $a_j=p_j$，$b_j=p_{j+1}$（$1\le j\le m$ 且 $j$ 为整数）
$4$	$32$	$n\le 20000$
$5$	$11$	无