### COCI 2006/2007, Contest #3

A bicycle race is being organized in a land far, far away. There are N town 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 ≤ N ≤ 10 000, 1 ≤ M ≤ 100 000), the number of towns and roads.

Each of the next M lines contains two different integers A and B, representing a road between towns A and 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".

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

```3
```

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

```inf
```

```31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
…
…
…
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2
```

### Output

```073741824
```

Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 32M

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (3/0)
My code got accepted here but got Wrong Answer on SPOJ. Here's a case where it went wrong:

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

Correct answer is "inf". (I don't want to spoil the problem for others so I won't describe what is special about this type of cases)

• (0/5)
Do not post test cases and answers into the comments. If you are referring to a certain test case then use the test case number

• (1/0)
He's not posting a PEG case, it's from SPOJ. Actually, this is pretty useful to check that your solution really is correct if you pass PEG tests, but a case like that isn't tested.