Gomgomi's Last-Minute Cramming

Time limit1sMemory limit1024 MB

Summary

Count the orders for watching N lectures under prerequisite relations that form a forest, modulo 10^9+7.

Level: Medium6 of 10
Topics: Tree, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

곰곰: 파스스

With the final exam approaching, Gomgomi has $N$ backlogged lectures to watch. The lectures are numbered from $1$ to $N$ in order. Each lecture has at most one lecture that must be watched before it. Gomgomi writes this relation as $a \rightarrow b$ , meaning lecture $a$ must be watched before lecture $b$ . The relations contain no cycles. The order in which Gomgomi watches all the lectures depends on these relations. Find the number of orders for watching all the lectures. Since the answer can be large, print it modulo $10^9+7$ .

Input

The first line contains the number of lectures $N$ and the number of relations $M$ . $(0 \leq M \lt N \leq 200\,000)$

Each of the next $M$ lines contains integers $a$ and $b$ , separated by a space. $(1 \leq a, b \leq N; a \neq b)$ This means lecture $a$ must be watched before lecture $b$ . The relations contain no cycles, and each lecture has at most one lecture that must be watched before it.

Output

Print the number of orders for watching all the lectures, modulo $10^9+7$ .

Examples3

Example 1
Input
```
5 4
1 2
2 4
2 5
4 3
```
Expected output
```
3
```
Example 2
Input
```
4 2
1 2
3 4
```
Expected output
```
6
```
Example 3
Input
```
2 0
```
Expected output
```
2
```