P4685 [IOI 2008] Linear Garden

Ramesses II has just returned victorious. To commemorate this victory, he decided to build a magnificent garden. The plants in this garden are arranged in a single line, stretching from his palace in Luxor all the way to the Karnak Temple. The only plants used are lotus and papyrus, because they represent Upper Egypt and Lower Egypt, respectively. The garden must contain $N$ plants and must be balanced. That is, for any segment chosen within the garden, the difference between the number of lotus and the number of papyrus in that segment must not exceed $2$. The garden can be represented as a string consisting of the letters `L` (lotus) and `P` (papyrus). For example, when $N=5$, there are $14$ possible balanced gardens. In lexicographical order, they are: `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 in lexicographical order and numbered starting from $1$. For example, when $N=5$, garden number $12$ is `PLPPL`. Write a program that, given the number of plants $N$ and a string representing a balanced garden, computes the garden’s index modulo $M$, where $M$ is a given integer. Note that in solving the problem, the value $M$ has no purpose other than simplifying the computation.

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

Your program should output to standard output a single integer between $0$ and $M-1$ (inclusive), on one line, representing the garden’s index modulo $M$.

There are test points worth 40 points where $N$ does not exceed $40$. For all test points, $1\le N\le 1,000,000$ and $7\le M \le 10,000,000$. ### Sample Explanation In the first sample, the actual index is 12. Therefore, the output is $12$ modulo $7$, which is $5$. Translated by ChatGPT 5