Balanced Garden Ranking

Ramses II has returned victorious and to commemorate his win he decided to build a spectacular garden. The garden consists of N plants arranged in a single row from his palace in Luxor to the Karnak Temple. Only two types of plants are used: the lotus (L) representing Upper Egypt and the papyrus (P) representing Lower Egypt.

The garden must be balanced. In a balanced garden, for any contiguous segment of plants, the difference between the number of lotus plants and papyrus plants is at most 2. In other words, if we denote by \(d(i)\) the difference between the number of L and P in the prefix up to position \(i\) (taking \(d(0)=0\)), then for the garden to be balanced we must have:

[ \max_{0\le i\le N} d(i) - \min_{0\le i\le N} d(i) \le 2. ]

All possible balanced gardens of length N can be sorted in lexicographical order (using the natural order where L is considered smaller than P), and are numbered starting from 1. For example, when N = 5, there are 14 balanced gardens and they appear in the following lexicographical order:

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

Thus, for N = 5 the 12th garden is PLPPL.

Your task is: Given N, an integer modulus M, and a balanced garden (a string of length N composed of characters L and P), determine its lexicographical rank modulo M (i.e. compute the rank, where the rank of the garden is defined as the number of balanced gardens that come before it in lexicographical order plus 1, then taken modulo M).

inputFormat

The input consists of two lines:

1. The first line contains two space-separated integers: N (the number of plants) and M (the modulus).
2. The second line contains a string of length N composed only of the characters L and P, representing a balanced garden.

outputFormat

Output a single integer, the lexicographical rank of the given garden modulo M.

sample

5 100
PLPPL

12