interzis

Interzis

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

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $interzis.in$ ...

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'$.

h2. Date de ieşire

În fişierul de ieşire $interzis.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. interzis.in |_. interzis.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
aaa
| 7

|
h3. 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$

== include(page="template/taskfooter" task_id="interzis") ==
 

== include(page="template/taskfooter" task_id="interzis") ==