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ă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$.

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

* 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

* Se vor acorda $10$ puncte din oficiu (testul 10 este primul exemplu)

h2. Exemplu