Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="spirt") ==
Mescheriakov vrea sa devine 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 increde. 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". 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!
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!
h3. Cerinta
h2. Cerinta
Scrie un program care rezolva problema lui Mescheriakov!
h2. Restricţii
* $1 ≤ N,M ≤ 100 000$
* Se garanteaza ca parantezarea din enunt este corecta (fiecare paranteza are pereche).
* $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
Nu exista diferente intre securitate.
Diferente intre topic forum:
