Problem Description

Ramses II has just returned victorious. To commemorate this victory, he decides to build a magnificent garden. The plants in this garden are arranged in a line, stretching from his palace in Luxor to the Temple of Karnak. The only plants planted are lotus and papyrus, as they represent Upper and Lower Egypt respectively.

The garden must contain $N$ plants and must maintain balance, meaning that in any segment of the garden, the difference between the number of lotus and papyrus plants cannot exceed 2.

The garden can be represented as a string of letters L (lotus) and P (papyrus). For example, when $N=5$, there are 14 possible balanced gardens, listed alphabetically as follows: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, and PPLPL.

All possible balanced gardens of a given length can be sorted alphabetically and numbered starting from 1. For example, when $N=5$, the 12th garden is PLPPL.

Write a program that, given the number of plants $N$ and a string representing a balanced garden, calculates the garden's number modulo $M$, where $M$ is a given integer. Note that the value $M$ is used only to simplify calculations and has no other role in the problem.

Input Format

The first line is an integer $N$, indicating the number of plants in the garden. The second line is an integer $M$. The third line is a string of length $N$ consisting of characters L or P, representing a balanced garden.

Output Format

Your program should output an integer between 0 and $M-1$ (inclusive), on a single line, representing the garden's number modulo $M$.

Sample Input and Output

Sample Input #1

5
7
PLPPL

Sample Output #1

5

Sample Input #2

12
10000
LPLLPLPPLPLL

Sample Output #2

39

Notes

There are test cases worth a total of 40 points where $N$ does not exceed 40.

For all test cases, $1 \leq N \leq 1,000,000$ and $7 \leq M \leq 10,000,000$.

Sample Explanation

In the first sample, the actual number is 12. Therefore, the output is 12 modulo 7, which is 5.

见题面 Input 部分

见题面 Output 部分