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

서브태스크

힌트