시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 91 | 61 | 52 | 64.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$로 나눈 나머지를 출력한다.
5 4 1 2 2 4 2 5 4 3
3
$(1, 2, 4, 3, 5), (1, 2, 4, 5, 3), (1, 2, 5, 4, 3)$으로 시청하는 3가지 방법이 존재한다.
4 2 1 2 3 4
6
다음과 같은 6가지 방법이 존재한다.
2 0
2