외계인의 세기

시간 제한8초메모리 제한512 MB

요약

손가락 N개와, 손가락 S가 굽으면 D도 반드시 굽는다는 규칙 M개가 주어질 때, 동시에 굽힐 수 있는 손가락 집합의 개수를 1000000007로 나눈 나머지로 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 동적 계획법, 위상 정렬, 조합론
정답자: 아직 제출이 없습니다

문제

나츠키와 친구들은 외계인에게 우주로 끌려갔고, 그곳에서 많은 외계인과 친구가 되었다. 우주 여행 중에 그녀는 외계인의 손이 인간의 손과 자주 다르다는 것을 알게 되었다. 일반적으로 어떤 종류의 외계인 손에는 N개의 손가락과 M개의 굽힘 규칙이 있다. 각 굽힘 규칙은 손가락 B가 굽으면 손가락 A도 항상 굽는다는 것을 나타낸다. 그러나 이 규칙이 손가락 A가 굽을 때 손가락 B도 굽는다는 것을 항상 의미하지는 않는다.

그녀는 손가락으로 수를 세면서 외계인 친구들이 손가락으로 몇 개의 수를 셀 수 있는지 궁금했다. 그러나 일부 친구의 규칙 집합이 너무 복잡해서 그녀는 그것을 계산할 수 없었다. 그녀를 위해 프로그램을 작성해 주겠는가?

입력

N M
S1 D1
S2 D2
.
.
.
SM DM

첫째 줄에는 두 정수 N과 M (1 ≤ N ≤ 1000, 0 ≤ M ≤ 1000)이 이 순서대로 주어진다. 다음 M개의 줄은 굽힘 규칙을 나타낸다. 각 줄에는 두 정수 Si와 Di가 이 순서대로 주어지며, 이는 손가락 Si가 굽을 때 손가락 Di가 항상 굽는다는 것을 의미한다. 어떤 손가락도 S에 두 번 이상 나타나지 않는다.

출력

외계인 친구들이 손가락으로 셀 수 있는 수의 개수를 계산하라. 답을 1000000007로 나눈 나머지를 한 줄에 출력하라.

예제3

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