[COCI2006-2007#3] BICIKLI

一场自行车比赛将要在一个遥远的地方上举行。

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

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

输出不同的路线的数量。 如果有无数条不同的路线，则输出 `inf`。 否则输出路线数对 $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

#### 数据规模与约定 对于 $100\%$ 的数据，$1\le n\leq 5\times 10 ^ 4$，$1\leq m\le 10^5$。 #### 说明 **题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T5 BICIKLI*** 感谢 @[ShineEternal](https://www.luogu.com.cn/user/45475) 提供的翻译。