Liniowy ogród

Limit pamięci: 64 MB

Ramzes II wrócił właśnie ze zwycięskiej bitwy. Aby uczcić swe zwycięstwo, postanowił założyć wspaniały ogród. W ogrodzie ma się znajdować długa rabata, ciągnąca się od jego pałacu w Luksorze aż do świątyni Karnak. Na rabacie będą rosły wyłącznie kwiaty lotosu i papirusu, jako że symbolizują one odpowiednio Górny i Dolny Egipt.

Na rabacie musi być dokładnie roślin. Ponadto, rabata musi być zbalansowana: w każdym jej spójnym fragmencie liczby roślin lotosu i papirusu mogą różnić się co najwyżej o 2.

Każdy możliwy układ roślin na rabacie można przedstawić jako napis złożony z liter 'L' (lotos) i 'P' (papirus). Na przykład dla istnieje 14 możliwych zbalansowanych układów rabaty. Są to, w kolejności alfabetycznej: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP i PPLPL.

Wszystkie opisy zbalansowanych rabat o ustalonej długości można uporządkować alfabetycznie, a następnie ponumerować, poczynając od 1. Na przykład dla rabatą numer 12 jest PLPPL.

Zadanie

Napisz program, który mając daną liczbę roślin oraz napis reprezentujący pewną zbalansowaną rabatę, wyznaczy numer przypisany tej rabacie modulo pewna podana liczba całkowita .
Zauważ, że wartość nie ma żadnego znaczenia w rozwiązaniu zadania, poza uproszczeniem obliczeń.

Ograniczenia

;
.

Wejście

Twój program powinien wczytać ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawierający liczbę całkowitą - liczbę roślin na rabacie.
• Drugi wiersz zawierający liczbę całkowitą .
• Trzeci wiersz zawierający napis złożony z znaków 'L' (lotos) lub 'P' (papirus) reprezentujący pewien zbalansowany układ roślin na rabacie.

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą między a (włącznie) - numer przypisany układowi roślin na rabacie podanemu na wejściu, modulo .

Punktacja

W testach wartych łącznie 40 punktów, nie przekracza 40.

Przykład

Dla danych wejściowych:

5
7
PLPPL

poprawną odpowiedzią jest:

5

Numerem przypisanym PLPPL jest 12, a zatem wynikiem jest 12 modulo 7, czyli 5.

Dla danych wejściowych:

12
10000
LPLLPLPPLPLL

poprawną odpowiedzią jest:

39