P4645 [COCI 2006/2007 #3] BICIKLI

A bicycle race is going to be held in a remote place.

There are $n$ towns in this place, numbered from $1$ to $n$, and there are $m$ **directed** roads connecting them. The race starts in town $1$ and ends in town $2$. The organizers want to know how many different routes there are in total.

The first line contains two integers $n, m$, with the meanings described above. The next $m$ lines each contain two integers $a, b$, describing a road from $a$ to $b$. There may be multiple roads between two towns.

Output the number of different routes. If there are infinitely many different routes, output `inf`. Otherwise, output the result modulo $10^9$.

#### Constraints For $100\%$ of the testdata, $1 \le n \le 5 \times 10^4$, $1 \le m \le 10^5$. #### Notes **Translated from [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T5 BICIKLI*.** Thanks to @[ShineEternal](https://www.luogu.com.cn/user/45475) for providing the translation. Translated by ChatGPT 5