Description

There are $n$ towns in this place, numbered from $1$ to $n$, and there are $m$ directed roads connecting them. The race starts in town $1$ and ends in town $2$.

The organizers want to know how many different routes there are in total.

Input Format

The first line contains two integers $n, m$, with the meanings described above.

The next $m$ lines each contain two integers $a, b$, describing a road from $a$ to $b$.

There may be multiple roads between two towns.

Output Format

Output the number of different routes.

If there are infinitely many different routes, output inf.

Otherwise, output the result modulo $10^9$.

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

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^4$, $1 \le m \le 10^5$.

Notes

Translated from COCI2006-2007 CONTEST #3 T5 BICIKLI.

Thanks to

Translated by ChatGPT 5