Propozitie

propozitie

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

Maria a gasit un sir de $N$ caractere ale alfabetului latin (caractere de la $a$ la $z$) despre care stie ca reprezinta o propozitie formata din unul sau mai multe cuvinte, din care au fost eliminate insa spatiile. Maria a mai aflat de la Gigel ca orice cuvant din propozitie contine cel mult $K$ vocale. Maria se intreaba acum in cate moduri diferite poate reconstitui propozitia initiala. Pentru ca intuieste ca sunt multe posibilitati, ea va cere voua sa aflati doar restul impartirii numarului total de posibilitati la $9001$.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $propozitie.in$ contine pe prima linie, separate de un singur spatiu, numerele $N$ si $K$, avand semnificatia din enunt. Pe urmatoarea linie se afla un sir de $N$ caractere, sirul gasit de Maria.

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

h2. Date de ieşire

În fişierul de ieşire $propozitie.out$ se va afisa un singur numar natural $Res$, care reprezinta restul impartirii numarului total de posibilitati de a forma o propozitie valida la $9001$.

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

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ 100$
* Vocalele din alfabetul latin sunt literele $a$, $e$, $i$, $o$ si $u$

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

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

| 3 1
  ana
| 3

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

|
h3. Explicaţie

Cele trei propozitii care se pot forma sunt: $a n a$, $a na$ si $an a$. Observati ca propozitia $ana$ nu este valida deoarece cuvantul $ana$ contine doua vocale.

...

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

3480