时间限制：1秒　　内存限制：256M

---

【题目描述】

　　一场自行车比赛将要在一个遥远的地方上举行。
　　这个地方有 \(n\) 个城镇，从 \(1\sim n\) 编号，其中有 \(m\) 条**单向**道路连接它们。比赛将在 \(1\) 号城镇开始并在 \(2\) 号城镇结束。
　　主办方想知道，一共有多少条不同的路线？

【输入格式】

　　输入第一行为两个整数 \(n,m\)，意义如题目描述所示。
　　接下来的 \(m\) 行，每行两个整数 \(a,b\)，描述一条从 \(a\) 到 \(b\) 的道路。
　　两个城镇间可以有多条道路。

【输出格式】

　　输出不同的路线的数量。如果有无数条不同的路线，则输出 inf。否则输出路线数对 \(10^9\) 取模的结果。

【输入输出样例1】

　Input

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

　Output

3

【输入输出样例2】

　Input

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

　Output

inf

【测试点性质】

　　对于 \(100\%\) 的数据，\(1\le n\leq 5\times 10 ^ 4\)，\(1\leq m\le 10^5\)。

【来源】

　　Mr.he