Una permutación de enteros ~1,2,\ldots,n~ se denomina hermosa si no existen elementos adyacentes cuya diferencia sea 1. Dado ~n~, tu tarea consiste en contar el número de permutaciones hermosas.

Entrada

La única línea de entrada contiene un entero ~n~.

Salida

Imprime el número de permutaciones hermosas de ~1,2,\ldots,n~ módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 1000~

Ejemplo de Entrada

 5

Ejemplo de Salida

14