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

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

#### Input Specification

The first line of input contains two integers and , the number of towns and roads.

Each of the next lines contains two different integers and , representing a road between towns and .

Towns may be connected by more than one road.

#### Output Specification

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

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

#### Sample Output 1

`3`

#### Sample Input 2

```
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3
```

#### Sample Output 2

`inf`

#### Sample Input 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
```

#### Sample Output 3

`073741824`

## Comments

wait nvm

Note that you have to print leading zeros for big numbers, otherwise it'll be marked

`WA`

.This comment is hidden due to too much negative feedback. Click here to view it.