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

Poveste şi cerinţă...

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.

h2. Date de intrare