균형 잡힌 일렬 정원

람세스 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$번부터 차례로 번호를 매길 수 있다. 이때 L이 P보다 앞선다. 예를 들어 $N = 5$에서 $12$번째 문자열은 PLPPL이다.

길이가 $N$인 균형 잡힌 정원 문자열이 주어지면, 그 문자열이 같은 길이의 모든 균형 잡힌 정원 문자열 가운데 사전순으로 몇 번째인지(순위)를 구하고, 그 순위를 정수 $M$으로 나눈 나머지를 출력하여라.

$M$은 계산을 쉽게 하기 위한 값일 뿐, 다른 의미는 없다.

첫째 줄에 심을 식물의 수 $N$이 주어진다. ($1 \le N \le 10^6$)

둘째 줄에 정수 $M$이 주어진다. ($7 \le M \le 10^7$)

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

주어진 정원 문자열의 사전순 순위를 $M$으로 나눈 나머지를 한 줄에 출력한다. 이 값은 $0$ 이상 $M$ 미만의 정수이다.

첫 번째 예시에서 PLPPL은 $N = 5$인 균형 잡힌 정원 문자열 가운데 사전순으로 $12$번째이다. 따라서 답은 $12$를 $7$로 나눈 나머지인 $5$이다.