¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8465

리어카 경주 1s 128MB

Problemas

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

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

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


Entrada

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

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

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


Salida

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

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


Ejemplo #1

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

Ejemplo #2

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

Ejemplo #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

Ejemplo #4

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

Ejemplo #5

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

Ejemplo #6

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


Fuente

COCI 2006/2007 Contest #3 5번

Debes iniciar sesión para escribir código.