Se organiza una carrera ciclista en un lugar muy lejano. Hay ~N~ pueblos, numerados del ~1~ al ~N~. También hay ~M~ carreteras de un solo sentido entre los pueblos. La carrera comenzará en el pueblo ~1~ y terminará en el pueblo ~2~.

¿De cuántas maneras diferentes se puede establecer la ruta?. Dos rutas se consideran diferentes si no utilizan exactamente las mismas carreteras.

Entrada

La primera línea de entrada contiene dos enteros ~N~ y ~M~ ~(1 \leq N \leq 10 000, 1 \leq M \leq 100 000)~, el número de pueblos y carreteras. Cada una de las siguientes ~M~ líneas contiene dos enteros diferentes, ~A~ y ~B~, que representan una carretera entre los pueblos ~A~ y ~B~. Los pueblos pueden estar conectados por más de una carretera.

Salida

Indique el número de rutas distintas que se pueden establecer en una sola línea. Si ese número tiene más de nueve dígitos, muestre solo los últimos nueve dígitos. Si hay infinitas rutas, salida "~inf~".

Ejemplo #1 de Entrada

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

Ejemplo #1 de Salida

3

Ejemplo #2 de Entrada

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

Ejemplo #2 de Salida

inf

Ejemplo #3 de Entrada

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

Ejemplo #3 de Salida

073741824

Croatian Open Competition in Informatics 2006/2007 Contest 3