Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - DNA-ketjut

DNA-ketjut


View task | Model solution | Statistics


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
Esimerkki

Syöte:
8

Tuloste:
47088