Xətti bağ

Ramesses II döyüşdən qalibiyyətlə qayıdıb. Qələbəsini qeyd etmək üçün o, möhtəşəm bir bağ salmaq qərarına gəlib. Bağ, Luksorda yerləşən sarayından Karnak məbədinə qədər uzanan uzun bir bitki sırasından ibarət olacaq. Bağda yalnız lotus və papirus bitkiləri olacaq, çünki bu bitkilər müvafiq olaraq Yuxarı və Aşağı Misiri simvollaşdırırlar.

Bağda məhz $n$ bitki olmalıdır. Bundan əlavə, bağ balanslı olmalıdır: bağın istənilən ardıcıl hissəsində lotus və papirus bitkilərinin sayı arasındakı fərq $2$-dən çox olmamalıdır.

Bağı 'L' (lotus) və 'P' (papirus) hərflərindən ibarət bir sətir kimi göstərmək olar. Məsələn, n = 5 üçün, $14$ müxtəlif balanslı bağ mövcuddur. Əlifba sırası ilə bunlar belədir: $\text{LLPLP}$, $\text{LLPPL}$, $\text{LPLLP}$, $\text{LPLPL}$, $\text{LPLPP}$, $\text{LPPLL}$, $\text{LPPLP}$, $\text{PLLPL}$, $\text{PLLPP}$, $\text{PLPLL}$, $\text{PLPLP}$, $\text{PLPPL}$, $\text{PPLLP}$ və $\text{PPLPL}$.

Müəyyən uzunluqdakı mümkün balanslı bağları əlifba sırasına görə düzərək və $1$-dən başlayaraq nömrələmək olar. Məsələn, n = 5 üçün $12$-ci bağ $\text{PLPPL}$ olur.

Proqram yazın ki, verilən bitki sayı $n$ və balanslı bağın təsvir olunduğu sətir verildikdə, bu bağa uyğun olan nömrəni (əlifba sırasına görə) $m$ modulunda hesablansın. Qeyd olunur ki, $m$-in dəyərinin yeganə məqsədi hesabatları sadələşdirməkdir. Məlumdur ki, 1 \leq n \leq 1\ 000\ 000, 7 \leq m \leq 10\ 000\ 000.