CSES - DNA-ketjut
  • Time limit: 1.00 s
  • Memory limit: 128 MB

DNA-ketju muodostuu merkeistä A, C, G ja T. Ketju on kiinnostava, jos missään kohdassa ei ole yli kahta samaa merkkiä peräkkäin.

Tehtäväsi on laskea, montako kiinnostavaa n merkin ketjua on olemassa.

Syöte

Syötteenä on kokonaisluku n.

Tuloste

Tulosta ketjujen määrä modulo 10^9+7.

Rajat

  • 1 \le n \le 10^{18}

Esimerkki

Syöte:

8

Tuloste:

47088