Рамзес Другий тільки що повернувся з переможної битви. Щоб увічнити свою перемогу, він вирішив побудувати величавий сад. Сад буде містити довгу лінію з рослин, яка буде протянутна вздовж всього шляху від його палацу в Луксорф до Карнакського храму. Сад буде складатись лише з лотосів та папірусів, оскільки вони символізують Верхній та Нижній Єгипет відповідно. Сад повинен містити рівно \textbf{n} рослин. Кріме того, він повинен бути збалансованим: на довільному неперервному відрізку саду кількість лотосів та папірусів не повинні відрізнятись більше, ніж на \textbf{2}. Сад может бути представлено у вигляді рядка літер '\textbf{L}' (лотос) та '\textbf{P}' (папірус). Наприклад, для \textbf{n = 5} можливі \textbf{14} збалансованих садів. В алфавітному порядку це сади: \textbf{LLPLP}, \textbf{LLPPL}, \textbf{LPLLP}, \textbf{LPLPL}, \textbf{LPLPP}, \textbf{LPPLL}, \textbf{LPPLP}, \textbf{PLLPL}, \textbf{PLLPP}, \textbf{PLPLL}, \textbf{PLPLP}, \textbf{PLPPL}, \textbf{PPLLP} та \textbf{PPLPL}. Можливі збалансовані сади даної довжини можуть бути впорядковані в алфавітному порядку і пронумеровані, починаючи з \textbf{1}. Наприклад, для \textbf{n = 5} сад з номером \textbf{12} -- це сад \textbf{PLPPL}. Напишіть програму, яка за заданою кількістю рослин \textbf{n} і рядком, який представляє збалансований сад, обчислює номер, присвоєний цьому саду, за модулем заданого цілого числа \textbf{m}. Слід відмітити, що для розв'язання задачі значення числа \textbf{m} не має нікого іншого змісту, крім як спрощення обчислень. Відомо, що \textbf{1 ≤ n ≤ 1 000 000},\textbf{ 7 ≤ m ≤ 10 000 000}. \InputFile Ваша програма повинна читати зі стандартного вводу дані у наступному форматі: • Рядок \textbf{1} містить ціле число \textbf{n} -- кількість рослин у саду. • Рядок \textbf{2} містить ціле число \textbf{m}. • Рядок \textbf{3} містить рядок з \textbf{n} символів '\textbf{L}' (лотос) та '\textbf{P}' (папірус), який представляє збалансований сад. \OutputFile Ваша програма повинна вивести у стандартний вивід єдиний рядок, що містить одне ціле число від \textbf{0} до \textbf{m - 1} включно -- номер, присвоєний саду, описаному у стандартному вводі, обчислений за модулем \textbf{m}.