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