Bittijono on merkkijono, joka muodostuu merkeistä 0 ja 1.

Uolevin mielestä bittijono on kaunis, jos siinä ei ole missään kohdassa kolmea tai useampaa samaa merkkiä peräkkäin.

Esimerkiksi bittijono 110101 on kaunis, kun taas bittijono 110001 ei ole.

Tehtäväsi on laskea, montako annetun pituista kaunista bittijonoa on olemassa.

Syöte

Syötteen ainoalla rivillä on kokonaisluku n: bittijonon pituus.

Tuloste

Ohjelmasi tulee tulostaa kauniiden n-merkkisten bittijonojen määrä modulo 10^9+7.

Rajat

• 1 \le n \le 10^5

Esimerkki

Syöte:

4

Tuloste:

10

Selitys: Kyseiset bittijonot ovat 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100 sekä 1101.