페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8465

리어카 경주 1s 128MB

문제

1번부터 N번까지 번호가 매겨져 있는 N개의 마을과 각 마을을 연결하는 M개의 일방통행 도로로 이루어진 나라가 있다.

이 나라에서는 리어카 경주 대회를 개최하려고 한다. 경주의 출발지는 1번 마을이고, 도착지는 2번 마을이다.

리어카 경주를 개최할 수 있는 경로의 수는 총 몇 가지가 있는지 구하는 프로그램을 작성하시오.


입력

첫째 줄에 두 정수 N과 M이 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)

다음 M개 줄에는 도로의 정보를 나타내는 A와 B가 주어진다. 이 정보는 A에서 B로 향하는 도로를 나타낸다.

두 마을이 하나 이상의 도로로 연결되어 있을 수도 있다.


출력

첫째 줄에 가능한 리어카 경주 대회 경로의 수를 10^9로 나눈 나머지를 출력한다.

만약, 경로의 수가 무한대인 경우에는 "inf"를 출력한다.


예제 #1

6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4
3

예제 #2

6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3
inf

예제 #3

31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
7 8
7 8
8 9
8 9
9 10
9 10
10 11
10 11
11 12
11 12
12 13
12 13
13 14
13 14
14 15
14 15
15 16
15 16
16 17
16 17
17 18
17 18
18 19
18 19
19 20
19 20
20 21
20 21
21 22
21 22
22 23
22 23
23 24
23 24
24 25
24 25
25 26
25 26
26 27
26 27
27 28
27 28
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2
73741824

예제 #4

6 6
1 3
3 2
4 3
5 4
6 5
4 6
1

예제 #5

6 6
1 3
3 2
3 4
5 4
6 5
4 6
1

예제 #6

5 5
1 3
3 2
3 4
5 3
4 5
inf


출처

COCI 2006/2007 Contest #3 5번
로그인해야 코드를 작성할 수 있어요.