일렬로 꾸미기(Linear Garden) timer 1s memory 128MB

람세스 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이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.