Fişierul intrare/ieşire:	spirt.in, spirt.out	Sursă	Algoritmiada 2012, Runda Finala
Autor	Andrei Grigorean	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Spirt

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!

Cerinta

Scrie un program care rezolva problema lui Mescheriakov!

Date de intrare

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.

Date de ieşire

În fişierul de ieşire spirt.out trebuie sa afisati un singur numar, raspunsul la problema, modulo 666013.

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!

Exemplu

Cum se trimit solutii?