시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB91615264.198%

문제

곰곰: 파스스

기말고사가 다가오는 곰곰이는 밀린 강의 $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$로 나눈 나머지를 출력한다.

예제 입력 1

5 4
1 2
2 4
2 5
4 3

예제 출력 1

3

$(1, 2, 4, 3, 5), (1, 2, 4, 5, 3), (1, 2, 5, 4, 3)$으로 시청하는 3가지 방법이 존재한다.

예제 입력 2

4 2
1 2
3 4

예제 출력 2

6

다음과 같은 6가지 방법이 존재한다.

  • $(1, 3, 2, 4)$
  • $(1, 3, 4, 2)$
  • $(1, 2, 3, 4)$
  • $(3, 1, 2, 4)$
  • $(3, 1, 4, 2)$
  • $(3, 4, 1, 2)$

예제 입력 3

2 0

예제 출력 3

2

출처

Contest > BOJ User Contest > 곰곰컵 > 제2회 곰곰컵 L번