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 10000$, $1 \le M \le 100000$), 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”.

-----Examples-----
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

见题面

见题面