Permutaatiot

• Time limit: 1.00 s
• Memory limit: 128 MB

Tehtäväsi on laskea, monellako tavalla luvuista $1,2,\ldots,n$ voidaan muodostaa permutaatio niin, että minkään kahden vierekkäisen luvun ero ei ole $1$.

Esimerkiksi kun $n=4$, vastaus on $2$, koska mahdolliset permutaatiot ovat $(2,4,1,3)$ ja $(3,1,4,2)$.

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Tulosta permutaatioiden määrä modulo $10^9+7$.

Rajat

• $1 \le n \le 1000$
  

Esimerkki

Syöte:
4

Tuloste:
2