Рамзес Второй только что вернулся с победоносной битвы. Чтобы увековечить свою победу, он решил построить величественный сад. Сад будет содержать длинную линию из растений, которая будет тянуться вдоль всего пути от его дворца в Луксоре до Карнакского храма. Сад будет состоять только из лотосов и папирусов, поскольку они символизируют Верхний и Нижний Египет соответственно.

   Сад должен содержать ровно 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.