균형잡힌 직선형 정원

람세스 2세가 전투에서 승리를 거두고 귀환했다. 그는 승리를 기리기 위해 웅장한 정원을 조성하기로 결심했다. 그래서 궁궐이 있는 Lubrr에서부터 시작해 Karnak 신전에 이르는 긴 길을 따라 식물을 일렬로 쭉 심을 예정이다. 심는 식물은 연꽃(L)과 파피루스(P) 이렇게 단 두 종류이다. 이들은 각각 이집트 북부와 남부의 상징이기 때문이다.

정원에는 그런 식으로 N개의 식물을 심는데, 종류별 식물 배치에 균형이 있어야 한다. 정원 내부의 어떤 연속적인 구간이라도 연꽃과 파피루스의 개수 차이가 2를 넘어서는 안 된다.

람세스가 세우고자 하는 정원은 L 아니면 P로 이루어진 문자열로 나타낼 수 있다. 예를 들어 N=5인 경우 위에서 제시한 균형을 갖춘 정원은 14가지가 있을 수 있다. (LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL)

그리고 특정 길이에 대해 균형을 갖춘 정원 식물 배치를 나타내는 문자열들은 알파벳 오름차순으로 나열하여 1부터 번호를 매길 수 있다. 가령 N=5의 경우, 12번에 해당하는 정원 문자열은 PLPPL이다.

길이가 N인 균형 잡힌 정원을 나타내는 어떤 문자열을 입력 받아 이것이 그 길이에 해당하는 전체 균형 잡힌 정원 문자열 중 오름차순으로 몇째 순서에 해당하는지 서열을 구하고, 이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.

첫째 줄에는 심을 식물의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 정수 M이 주어진다. (7 ≤ M ≤ 10,000,000)

셋째 줄에는 길이가 N이며, L(연꽃)과 P(파피루스)로 이루어진 균형 잡힌 정원을 나타내는 문자열이 주어진다.

0 이상 M 미만의 정수 하나를 출력한다.

입력에서 주어진 정원 문자열의 오름차순 서열을 M으로 나눈 나머지의 값이다.

예제 입력에서 PLPPL은 사실 12번째에 있는 정원 배열이다. 그래서 12를 7로 나눈 나머지인 5를 정답으로 한다.