Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Este verano Fito se va de vacaciones a un parque de atracciones muy famoso y está tan emocionado que no quiere perder ni un segundo de diversión. El parque tiene muchas atracciones y Fito después de mucho trabajo ha elegido N de ellas para visitarlas el primer día. Fito ya compró los tiques necesarios y está decidido a participar en las $N$ atracciones, una vez en cada una. Desde cualquier atracción se puede ir a otra pero Fito tiene cierta preferencia en el camino que quiere hacer. Las preferencias de Fito son pares de atracciones que quiere visitar de forma consecutiva, por ejemplo si el par es la atracción 1 y la 3 entonces él quiere visitar la atracción 1 y después la 3 o primero la 3 y después la 1. Ayuda a Fito a contar la cantidad de formas en que puede visitar las $N$ atracciones, sin repetir visitas y que se cumplan todas las preferencias de Fito.

Input

Output

La salida es una línea con la cantidad de caminos que puede hacer Fito módulo $1,000,000,007$.

Sample test(s)