곰곰이의 벼락치기

시간 제한1초메모리 제한1024 MB

요약

선행 관계가 주어진 N개의 강의를 들을 수 있는 순서의 개수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 6점
유형: 트리, 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

곰곰: 파스스

기말고사가 다가오는 곰곰이는 밀린 강의 $N$ 개를 봐야 한다. 강의는 $1$ 번부터 $N$ 번까지 차례대로 번호가 붙어 있다. 모든 강의에는 그 강의를 보기 전에 먼저 봐야 하는 강의가 최대 하나 있다. 곰곰이는 이 관계를 $a \rightarrow b$ 로 나타낸다. 강의 $a$ 를 봐야 강의 $b$ 를 볼 수 있다는 뜻이다. 강의 관계에는 사이클이 없다. 관계에 따라 모든 강의를 보는 순서가 여러 가지일 수 있다. 모든 강의를 보는 순서의 가짓수를 구한다. 답이 커질 수 있으므로 $10^9+7$ 로 나눈 나머지를 출력한다.

입력

첫째 줄에 강의 수 $N$ 과 강의 관계 수 $M$ 이 주어진다. $(0 \leq M \lt N \leq 200\,000)$

둘째 줄부터 $M$ 개의 줄에 강의 관계를 나타내는 정수 $a$ 와 $b$ 가 공백으로 구분되어 주어진다. $(1 \leq a, b \leq N; a \neq b)$ 강의 $b$ 를 보려면 강의 $a$ 를 먼저 봐야 한다는 뜻이다. 강의 관계에는 사이클이 없으며, 모든 강의에는 먼저 봐야 하는 강의가 최대 하나 있다.

출력

모든 강의를 보는 순서의 가짓수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
5 4
1 2
2 4
2 5
4 3
```
예상 출력
```
3
```
예제 2
입력
```
4 2
1 2
3 4
```
예상 출력
```
6
```
예제 3
입력
```
2 0
```
예상 출력
```
2
```