Code Submission Evaluation System Login

Datatähti-valmennus

Permutaatiot


Task | Statistics


CSES - 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
Esimerkki

Syöte:
4

Tuloste:
2