Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | aiafarapalindroame.in, aiafarapalindroame.out | Sursă | Grigore Moisil 2017, 10 |
| Autor | Alex Cociorva | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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ă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.
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
Exemplu
| aiafarapalindroame.in | aiafarapalindroame.out | Explicaţii |
|---|---|---|
| 2 | 676 | test |
| 100 | 873567312 | test |
Explicaţie
...
