곰곰이의 벼락치기

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

요약

각 강의에 선수 강의가 최대 하나씩 있는 N개의 강의를 모두 듣는 순서의 가짓수를 10^9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 위상 정렬, 조합론, 트리
정답자: 아직 제출이 없습니다

문제

곰곰: 파스스

기말고사가 다가오는 곰곰이는 밀린 강의 $N$ 개를 봐야 한다. 강의는 $1$ 번부터 $N$ 번까지 차례대로 번호가 붙어 있으며, 모든 강의에 대해서 해당 강의를 보기 전에 먼저 봐야 하는 강의가 최대 하나 존재한다. 곰곰이는 이러한 강의 간의 관계를 $a \rightarrow b$ 로 나타냈으며, 이는 강의 $b$ 를 보려면 강의 $a$ 를 먼저 봐야 한다는 의미이다. 이러한 강의 간의 관계가 사이클을 이루는 경우는 존재하지 않는다. 강의 간의 관계에 따라서 모든 강의를 보는 순서는 다양할 수 있다. 모든 강의를 보는 순서의 가짓수가 몇 가지인지 구해주자. 답이 커질 수 있으니 $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
```