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 nn merkin ketjua on olemassa.

Syöte

Syötteenä on kokonaisluku nn.

Tuloste

Tulosta ketjujen määrä modulo 109+710^9+7.

Rajat

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

Esimerkki

Syöte:

8

Tuloste:

47088