시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB218653930.000%

문제

상욱이는 레이싱 결과 맞추기를 좋아한다. 상욱이가 레이싱 결과를 맞추는 방법은 이전 경기에서 A란 선수가 B란 선수를 이긴 적이 있으면, A는 B를 무슨일이 있어도 이번 레이스에서 항상 이긴다고 가정하고 경기 결과를 예측 하는 방법이다.

하지만 상욱이는 위와 같은 방법으로는 경기 결과가 하나로 결정되지 않는다는 것을 깨달았다.

예를 들어, 이번 레이스경기에 참가하는 자동차의 수가 4개이고, 상욱이가 알고있는 예전의 경기결과가 1이 2를 이기고, 1이 3을 이긴다면, 상욱이가 예측할 수 있는 레이스의 결과는 4123, 4132, 1423, 1432, 1243, 1342, 1234, 1324로 총 8가지이다.

자동차의 수와, 상욱이가 알고잇는 예전 경기 결과가 주어졌을 때, 현재 가능한 경기결과의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 이번 레이스에 참가하는 자동차의 수 N이 주어진다. N은 30보다 같거나 작은 자연수이다. 둘째 줄에 상욱이가 알고있는 예전 경기 결과의 수 M이 주어진다. M은 15보다 같거나 작은 자연수 또는 0이다. 셋째 줄부터 M개의 줄에는 예전 경기 결과가 주어진다. 예전 경기 결과는 A B 이렇게 주어지는데, A가 B를 항상 이긴다는 뜻이다. 자동차의 번호는 1부터 시작하며, N까지 하나씩 매겨져 있다.

출력

첫째 줄에 상욱이가 예상할 수 있는 경기 결과의 수를 1,000,003으로 나눈 나머지를 출력한다. 만약 예전 경기 결과 모순(1이 2를 이기고, 2가 1을 이기는 상황, 즉 경기결과를 예상할 수 없는 상황)이라면, 0을 출력한다.

예제 입력 1

3
1
2 3

예제 출력 1

3

예제 입력 2

4
2
1 2
1 3

예제 출력 2

8

예제 입력 3

10
3
2 3
3 4
4 2

예제 출력 3

0

예제 입력 4

30
0

예제 출력 4

90317

힌트

가능한 경기결과는 123 213 231 이다.

출처