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