Problem Background

A bicycle race is to be held in a distant location.

Problem Description

This location has $n$ towns numbered from $1$ to $n$, connected by $m$ one-way roads. The race will start in town $1$ and end in town $2$.

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

Input Format

The first line of input contains two integers $n$ and $m$, as described in the problem statement.

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

There can 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 number of routes modulo $10^9$.

Sample Input and Output

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

Notes

Data Size and Constraints

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

Notes

Translated from COCI2006-2007 CONTEST #3 T5 BICIKLI

Thanks to @ShineEternal for the translation.

见题面 Input 部分

见题面 Output 部分