Fişierul intrare/ieşire:interzis.in, interzis.outSursăAlgoritmiada 2013, Runda 1
AutorCosmin Silvestru NegruseriAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Interzis

Sa se numere cate siruri de N caractere, care contin doar caracterele 'a' si 'b' exista, cu conditia ca aceste siruri sa nu contina ca subsecventa un sir fixat de lungime L.

Date de intrare

Fişierul de intrare interzis.in contine pe prima linie numerele N si L cu semnificatia din enunt. Pe urmatoarea linie se gaseste sirul de lungime L, compus din caracterele 'a' si 'b'.

Date de ieşire

În fişierul de ieşire interzis.out se va gasi numarul cerut de siruri, modulo 101267.

Restricţii

  • 1 ≤ N ≤ 15000
  • 0 ≤ L ≤ 1000
  • Pentru 80% din teste L ≤ 50

Exemplu

interzis.ininterzis.out
3 3
aaa
7

Explicaţie

Toate sirurile solutie trebuie sa nu continta ca subsecventa sirul 'aaa'. Astfel, cele 7 siruri vor fi:
aab
aba
abb
baa
bab
bba
bbb

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?