24944번 - Misspelling 서브태스크다국어

Some time ago, President K had a string $S$ of length $N$ consisting of lower case characters. But, he forgot it. He had a dictionary which contains misspellings of several kinds, and he once took a look at the dictionary to check the misspellings of the string $S$. Now, he remembers that the following is true for the string $S$.

• Let $T_i$ ($1 ≤ i ≤ N$) be the string obtained from $S$ by deleting the $i$-th character and removing the gap. For each $j$ ($1 ≤ j ≤ M$), the relation $T_{A_j} ≤ T_{B_j}$ holds.

Here, $T_{A_j} ≤ T_{B_j}$ means either $T_{A_j}$ is equal to $T_{B_j}$, or $T_{A_j}$ is smaller than $T_{B_j}$ in the lexicographic order (alphabetical order).

Write a program which, given information on the string $S$ remembered by President K, calculates the number of strings $S$ modulo $1\,000\,000\,007$ which do not contradict given information.

Read the following data from the standard input. Given values are all integers.

$\begin{align*} & N \, M \\ & A_1 \, B_1 \\ & A_2 \, B_2 \\ & \vdots \\ & A_M\, B_M \end{align*}$

Write one line to the standard output. The output should contain the number of strings $S$ modulo $1\,000\,000\,007$ which do not contradict given information.

• $2 ≤ N ≤ 500\,000$.
• $1 ≤ M ≤ 500\,000$.
• $1 ≤ A_j ≤ N$ ($1 ≤ j ≤ M$).
• $1 ≤ B_j ≤ N$ ($1 ≤ j ≤ M$).
• $A_j \ne B_j$ ($1 ≤ j ≤ M$).
• $(A_j , B_j) \ne (A_k, B_k)$ ($1 ≤ j < k ≤ M$).