Balanced Garden in a Row

Ramesses II has returned victorious from battle and, to celebrate, decides to build a magnificent garden. Along the long road that runs from the palace at Lubrr to the temple at Karnak, he will plant a single row of plants. Only two kinds of plants are available: the lotus (L) and the papyrus (P), because they are the symbols of Lower and Upper Egypt respectively.

He plants $N$ plants in this way, and the arrangement of the two kinds must be balanced. Balanced means that for every contiguous segment of the garden, the difference between the number of lotuses and the number of papyri inside it never exceeds $2$.

Thus a garden can be written as a single string of L and P. For example, when $N = 5$ there are exactly $14$ balanced gardens:

LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL

If we list all balanced garden strings of the same length in ascending (lexicographic) order, we can number them starting from $1$, where L comes before P. For example, when $N = 5$ the $12$th string is PLPPL.

Given a balanced garden string of length $N$, find its rank — its position in lexicographic order among all balanced garden strings of the same length — and print that rank modulo the integer $M$.

$M$ is provided only to make the computation easier and has no other meaning.

The first line contains the number of plants $N$. ($1 \le N \le 10^6$)

The second line contains an integer $M$. ($7 \le M \le 10^7$)

The third line contains a balanced garden string of length $N$, made up of L (lotus) and P (papyrus).

Print, on a single line, the lexicographic rank of the given garden string modulo $M$. This value is an integer in the range from $0$ to $M - 1$.

In the first example, PLPPL is the $12$th balanced garden string of length $N = 5$ in lexicographic order. Therefore the answer is $12 \bmod 7 = 5$.