== include(page="template/taskheader" task_id="spirt") ==
Poveste şi cerinţă...
Mescheriakov vrea sa devina producator de alcool. Si ce produs are un procentaj mai mare de alcool ca spirtul? Astfel, Mescheriakov si-a cumparat o fabrica de spirt, si vrea sa se apuce cat mai repede de productie, insa are nevoie de un aghiotant de incredere. El vrea sa va testeze cu urmatoarea problema: "Dandu-se o parantezare de lungime $N$ si un numar oarecare de culori, $M$, sa se coloreze fiecare paranteza cu o culoare dintre cele $M$, cu proprietatea ca doua paranteze care fac parte din aceeasi pereche sau care sunt adiacente nu au voie sa aiba aceeasi culoare. Se cere numarul de colorari ale aceestei parantezari modulo **666013**". Mescheriakov vrea sa-si aleaga ca aghiotant pe cel care va raspunde la problema de mai sus, dupa ce a baut o cantitate maxima de spirt. Cum tu vrei sa fii sigur ca obtii postul, ai nevoie de ajutorul unui calculator!
h2. Cerinta
Scrie un program care rezolva problema lui Mescheriakov!
h2. Date de intrare
Fişierul de intrare $spirt.in$ ...
Fişierul de intrare $spirt.in$ contine pe prima linie doua numere naturale $N$ si $M$, cu semnificatia din enunt. Pe a doua linie a fisierului de intrare se va gasi un sir de paranteze de lungime $N$, descriind parantezarea lui Mescheriakov.
h2. Date de ieşire
În fişierul de ieşire $spirt.out$ ...
În fişierul de ieşire $spirt.out$ trebuie sa afisati un singur numar, raspunsul la problema, modulo **666013**.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $3 ≤ M ≤ 100 000$
* Pentru $20%$ din teste $1 ≤ N ≤ 30$ si $1 ≤ M ≤ 10$
* Pentru alte $20%$ din teste $1 ≤ N, M ≤ 100$
* Se garanteaza ca parantezarea din enunt este corecta (fiecare paranteza deschisa are pereche o paranteza inchisa de dupa ea).
* Autorul acestei probleme, desi in contradictie cu Mescheriakov, va sfatuieste sa nu beti spirt!
h2. Exemplu
table(example). |_. spirt.in |_. spirt.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 4
()
| 12
|
| 4 4
(())
| 84
|
| 4 4
()()
| 108
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="spirt") ==
== include(page="template/taskfooter" task_id="spirt") ==
