Interzis

interzis

== include(page="template/taskheader" task_id="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$.

Poveste şi cerinţă...

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

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

h2. Date de ieşire

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

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

h2. Restricţii

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

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

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

| 3 3
aaa
| 7

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

|
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") ==