Problem 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 has forgotten it. He also had a dictionary containing various incorrect spellings, which he had once looked through. Now, he confirms that \( S \) meets the following conditions:

• Let \( T_i \) (\( 1 \le i \le N \)) be the string obtained by removing the \( i \)-th character from \( S \) and concatenating the remaining characters. For each \( j \) (\( 1 \le j \le M \)), \( T_{A_j} \le T_{B_j} \) holds.

Here, \( T_{A_j} \le T_{B_j} \) means \( 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 above information about \( S \) from President K, outputs the number of possible \( S \), modulo \( 10^9+7 \).

Input Format

The first line contains two positive integers \( N \) and \( M \), representing the length of \( S \) and the number of constraints, respectively.

The following \( M \) lines each contain two positive integers \( A_j \) and \( B_j \), representing a constraint.

Output Format

A single line containing a non-negative integer, representing the number of possible \( S \) modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

3 2
1 3
3 2

Sample Output #1

5876

Sample Input #2

5 6
1 2
1 5
2 4
5 4
5 3
4 3

Sample Output #2

656981

Sample Input #3

10 9
3 6
4 6
6 7
7 9
10 8
9 8
8 5
5 2
5 1

Sample Output #3

206289833

Sample Input #4

7 6
1 3
3 4
4 6
6 5
5 7
7 2

Sample Output #4

7125651

Sample Input #5

5 4
2 4
4 3
3 5
5 1

Sample Output #5

61451

Notes

[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 \( S \). Thus, 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 meets the constraints of all subtasks.

[Sample Explanation #2]

This sample meets the constraints of subtasks \( 1, 2, 4, 5 \).

[Sample Explanation #3]

The result before modulo is \( 824,206,295,601 \), so the output is \( 206,289,833 \).

This sample meets the constraints of subtasks \( 1, 2, 4, 5 \).

[Sample Explanation #4]

This sample meets the constraints of all subtasks.

[Sample Explanation #5]

This sample meets the constraints of all subtasks.

[Data Range]

For all data, the following conditions are satisfied:

• \( 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 \)).

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分