Hamiltonian Flights.


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Hay n ciudades y m conexiones aéreas entre ellas. Quieres viajar de Syrjälä a Lehmälä de forma que visites cada ciudad exactamente una vez. ¿Cuántas rutas posibles hay?

Entrada

La primera línea de entrada tiene dos números enteros n y m: el número de ciudades y vuelos. Las ciudades se numeran 1,2,m,n. La ciudad 1 es Syrjälä, y la ciudad n es Lehmälä.

Luego, hay m líneas que describen los vuelos. Cada línea tiene dos enteros a y b: hay un vuelo de la ciudad a a la ciudad b. Todos los vuelos son de ida.

Salida

Imprime un entero: el número de rutas módulo 10^9+7.

Restricciones

  • 2 \leq n \leq 20
  • 1 \leq m \leq n^2
  • 1 \leq a,b \leq n

Ejemplo de Entrada

4 6
1 2
1 3
2 3
3 2
2 4
3 4

Ejemplo de Salida

2

Comments

There are no comments at the moment.