Fişierul intrare/ieşire:aiafarapalindroame.in, aiafarapalindroame.outSursăGrigore Moisil 2017, 10
AutorAlex CociorvaAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

Date de intrare

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

Date de ieşire

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 109 + 7 ).

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)

Exemplu

aiafarapalindroame.inaiafarapalindroame.outExplicaţii
2
676
Există 262 = 676 şiruri posibile şi toate respectă proprietatea cerută de Bulănel.
100
873567312
Va trebui să ne credeţi pe cuvânt.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?