Después de la última guerra de los cinco ejércitos, Sauron quiere hacer su ejército más poderoso. Para ello ha encontrado un error que necesita ser corregido, los soldados están cansados de ver al mismo soldado precedente en la línea. Entonces necesita saber de cuántas maneras puede ordenar cada fila para que ningún soldado vea al mismo soldado precedente de la última guerra. Dada la línea de N soldados calcular la cantidad de arreglos que cumplen las reglas anteriores.

Especificación de entrada

La única línea de entrada contiene un entero. ~N (1 <= N <= 500)~.

Especificación de salida

Imprime la línea con la cantidad de arreglos. mod ~10^9 + 7 (1000000007)~.

Ejemplo de entrada

3

Ejemplo de salida

3

Sugerencia(s)

Para el ejemplo de entrada, las posibles permutaciones son: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Si se utilizó la primera permutación en la última guerra, las posibles permutaciones que cumplen las reglas son: [1,3,2], [2,1,3], [3,2,1].