# Problem A

Bicikli

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 |