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