== include(page="template/taskheader" task_id="aiafarapalindroame") ==
Pentru că nu îi plac enunţurile lungi, Bulănel vă oferă urmatoarea problemă:

Dându-se un număr natural N, calculaţi câte şiruri formate din N caractere ale alfabetului englez există astfel încât şirurile să nu conţină subsecvenţe palindrom de lungime mai mare sau egala cu 3. Rezultatul va fi afişat modulo 109 + 7.
De exemplu, şirul ‘cabad’ nu se va numără deoarece conţine subsecvenţa ‘aba’ care este palindrom de lungime mai mare sau egala cu 3. Pe de altă parte, şirul ‘abccef’ este unul valid deoarece nu conţine subsecvenţe palindroame de lungime mai mare sau egala cu 3.

 
Dându-se un număr natural $N$, calculaţi câte şiruri formate din $N$ caractere ale alfabetului englez există astfel încât şirurile să nu conţină subsecvenţe palindrom de lungime mai mare sau egala cu $3$. Rezultatul va fi afişat $modulo 10^9^ + 7$.
 
De exemplu, şirul $cabad$ nu se va număra deoarece conţine subsecvenţa $aba$ care este palindrom de lungime mai mare sau egala cu $3$. Pe de altă parte, şirul $abccef$ este unul valid deoarece nu conţine subsecvenţe palindroame de lungime mai mare sau egala cu $3$.

h2. Date de intrare

Fişierul de intrare $aiafarapalindroame.in$ ...

Fişierul de intrare $aiafarapalindroame.in$ conţine pe prima linie un număr natural $N$.

h2. Date de ieşire

În fişierul de ieşire $aiafarapalindroame.out$ ...

Fişierul de ieşire $aiafarapalindroame.out$ conţine un singur număr reprezentând numărul de şiruri care respectă proprietatea cerută de Bulănel ( $modulo 10^9^ + 7$ ).

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1 000 000 000$
* Pentru teste în valoare de $10$ de puncte $N ≤ 5$
* Pentru teste în valoare de $70$ de puncte $N ≤ 1 000 000$
* Alfabetul englez contine $26$ litere (literele de la a la z)
* Problema va fi evaluată pe teste în valoare de $90$ de puncte
* Se vor acorda $10$ puncte din oficiu (testul 10 este primul exemplu)

h2. Exemplu

table(example). |_. aiafarapalindroame.in |_. aiafarapalindroame.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. aiafarapalindroame.in |_. aiafarapalindroame.out |_. Explicaţii |
| 2
| 676
| Există $26^2^ = 676$ şiruri posibile şi toate respectă proprietatea cerută de Bulănel.
|
| 100
| 873567312
| Va trebui să ne credeţi pe cuvânt.
|

...

== include(page="template/taskfooter" task_id="aiafarapalindroame") ==