Background

JOISC2022 D1T3

Problem Description

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$.

Input Format

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 Format

Output one line containing one non-negative integer, the number of possible strings $S$ modulo $10^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

Hint

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:

Translated by ChatGPT 5