P9522 [JOIST 2022] Misspelling

JOISC2022 D1T3

Once upon a time, President K had a string $S$ of length $N$, consisting only of lowercase letters. However, he forgot it. He also has a dictionary that contains various kinds of misspellings. He once read that dictionary, and now he is sure that $S$ satisfies the following condition: - Let $T_i$ $(1\le i\le N)$ be the string obtained by deleting the $i$-th character of $S$ and concatenating the remaining parts. For every $j$ $(1\le j\le M)$, it holds that $T_{A_j} \le T_{B_j}$. Here, $T_{A_j} \le T_{B_j}$ means that $T_{A_j}$ is equal to $T_{B_j}$, or $T_{A_j}$ is lexicographically smaller than $T_{B_j}$. Write a program that, given the information above about $S$, outputs the number of possible strings $S$, modulo $10^9+7$.

The first line contains two positive integers $N, M$, representing the length of $S$ and the number of constraints. The following $M$ lines: the $j$-th line $(1 \le j \le M)$ contains two positive integers $A_j, B_j$, representing one constraint.

Output one line containing one non-negative integer, the number of possible strings $S$ modulo $10^9+7$.

**Sample Explanation #1.** For example, if $S=\texttt{bab}$, then $T_1 = \texttt{ab}, T_2 = \texttt{bb}, T_3 = \texttt{ba}$. It satisfies $T_1 \le T_3$ and $T_3 \le T_2$. Therefore, this $S$ is valid. It can be proven that there are $5876$ valid strings $S$ in total. Hence, the output is $5876$. On the other hand, if $S=\texttt{aab}$, then $T_1 = \texttt{ab}, T_2 = \texttt{ab}, T_3 = \texttt{aa}$. It does not satisfy $T_1 \le T_3$. Therefore, this $S$ is invalid. This sample satisfies the constraints of all subtasks. **Sample Explanation #2.** This sample satisfies the constraints of subtasks $1,2,4,5$. **Sample Explanation #3.** The result before taking modulo is $824\,206\,295\,601$, so the output is $206\,289\,833$. This sample satisfies the constraints of subtasks $1,2,4,5$. **Sample Explanation #4.** This sample satisfies the constraints of all subtasks. **Sample Explanation #5.** This sample satisfies the constraints of all subtasks. **Constraints.** For all testdata, it holds that: - $2 \le N \le 500\,000$. - $1 \le M \le 500\,000$. - $1 \le A_j,B_j \le N$ $(1 \le j \le M)$. - $A_j\ne B_j$ $(1 \le j \le M)$. - $(A_j,B_j)\ne(A_k,B_k)$ $(1 \le j < k \le M)$. The detailed additional constraints and scores for subtasks are shown in the table below: |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$1$|$N \le 10$|$8$| |$2$|$N \le 200$|$20$| |$3$|There exists a permutation $P$ of $\{1,2,\dots,N\}$ such that $A_j = P_j, B_j = P_{j+1}$ $(1 \le j \le M=N-1)$|$29$| |$4$|$N \le 20\,000$|$32$| |$5$|No additional constraints|$11$| Translated by ChatGPT 5