题目背景

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

题目描述

这个地方有 $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 CONTEST #3 T5 BICIKLI

感谢