OpenKattis
Kattis Set 12

#### Start

2020-04-06 05:15 AKDT

## Kattis Set 12

#### End

2020-04-13 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -440 days 22:57:47

164:15:00

0:00:00

# Problem IBicikli

A bicycle race is being organized in a land far, far away. There are $N$ towns in the land, numbered $1$ through $N$. There are also $M$ one-way roads between the towns. The race will start in town $1$ and end in town $2$.

How many different ways can the route be set? Two routes are considered different if they do not use the exact same roads.

## Input

The first line of input contains two integers $N$ and $M$ ($1 \le N \le 10\, 000$, $1 \le M \le 100\, 000$), the number of towns and roads.

Each of the next $M$ lines contains two different integers $A$ and $B$, representing a road from town $A$ to town $B$.

Towns may be connected by more than one road.

## Output

Output the number of distinct routes that can be set on a single line. If that number has more than nine digits, output only the last nine digits of the number. If there are infinitely many routes, output “inf”.

Sample Input 1 Sample Output 1
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

3

Sample Input 2 Sample Output 2
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3

inf

Sample Input 3 Sample Output 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

073741824