Лінійний сад

Рамзес II щойно повернувся з перемогою з битви. Щоб увіковічнити свою перемогу, він вирішив створити величний сад. Сад складатиметься з довгого ряду рослин, який простягатиметься від його палацу в Луксорі до храму в Карнаці. У саду будуть лише лотоси й папіруси, оскільки вони символізують Верхній і Нижній Єгипет відповідно.

У саду має бути рівно $n$ рослин. Додатково, він має бути збалансований: у будь-якому підрядку саду кількість лотосів і папірусів не повинна відрізнятися більше ніж на $2$.

Сад можна представити у вигляді рядка з літер 'L' (лотос) і 'P' (папірус). Наприклад, для n = 5 існує $14$ можливих збалансованих садів. В алфавітному порядку це: $\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}$ та $\text{PPLPL}$.

Можливі збалансовані сади певної довжини можна впорядкувати за алфавітом і пронумерувати, починаючи з $1$. Наприклад, для n = 5 сад під номером $12$ — це $\text{PLPPL}$.

Напишіть програму, яка, маючи кількість рослин $n$ та рядок, що представляє збалансований сад, обчислює номер, який відповідає цьому саду, за модулем заданого числа $m$. Зверніть увагу, що у розв'язанні значення $m$ має значення лише з погляду спрощення обчислень. Відомо, що 1 \leq n \leq 1\ 000\ 000, 7 \leq m \leq 10\ 000\ 000.