在一个遥远的国度，正在举办一场自行车比赛。这个国度有 $N$ 个城镇，编号为 $1$ 到 $N$。城镇之间有 $M$ 条单向道路。比赛将从 $1$ 号城镇开始，在 $2$ 号城镇结束。

一共有多少种不同的比赛路线？如果两条路线使用的道路不完全相同，则认为它们是不同的。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 10\,000$，$1 \le M \le 100\,000$），分别表示城镇的数量和道路的数量。

接下来的 $M$ 行，每行包含两个不同的整数 $A$ 和 $B$，表示一条从城镇 $A$ 到城镇 $B$ 的单向道路。

城镇之间可能存在多条道路连接。

输出格式

在单行中输出可以设置的不同路线的数量。如果该数量的位数超过九位，则仅输出该数字的最后九位。如果有无限多种路线，则输出 inf。

样例

输入样例 1

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

输出样例 1

3

输入样例 2

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

输出样例 2

inf

输入样例 3

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

输出样例 3

073741824