Bicikli P47358

Se organiza una carrera ciclista en un país muy, muy lejano. Hay N pueblos, numerados del 1 al N, y M carreteras de sentido único que los unen. La carrera empieza en el pueblo 1 y acaba en el pueblo 2.

¿Cuántas rutas distintas es posible establecer entre ambos pueblos? Dos rutas son distintas si no usan las mismas carreteras, en el mismo orden exacto.

Entrada

La primera línea contiene dos enteros N (entre 1 y 10000) y M (entre 1 y 100000), el número de pueblos y carreteras.

Las M restantes líneas contienen dos enteros distintos A y B, representando una carretera entre el pueblo A y el B. El mismo par de pueblos puede estar conectado por más de una carretera.

Salida

Escribe una línea con el número de rutas distintas que pueden establecerse entre los pueblos 1 y 2. Si este número tiene más de 9 dígitos, escribe las últimas nueve cifras. Si hay un número infinito de rutas, escribe “inf”.