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

   Сад повинен містити рівно 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 не має нікого іншого змісту, крім як спрощення обчислень. Відомо, що 1 ≤ n ≤ 1 000 000, 7 ≤ m ≤ 10 000 000.

   Вхідні дані

   Ваша програма повинна читати зі стандартного вводу дані у наступному форматі:
  • Рядок 1 містить ціле число n – кількість рослин у саду.
  • Рядок 2 містить ціле число m.
  • Рядок 3 містить рядок з n символів 'L' (лотос) та 'P' (папірус), який представляє збалансований сад.

   Вихідні дані

   Ваша програма повинна вивести у стандартний вивід єдиний рядок, що містить одне ціле число від 0 до m - 1 включно – номер, присвоєний саду, описаному у стандартному вводі, обчислений за модулем m.