Рамзес Второй только что вернулся с победоносной битвы. Чтобы увековечить свою победу, он решил построить величественный сад. Сад будет содержать длинную линию из растений, которая будет тянуться вдоль всего пути от его дворца в Луксоре до Карнакского храма. Сад будет состоять только из лотосов и папирусов, поскольку они символизируют Верхний и Нижний Египет соответственно. Сад должен содержать ровно \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}.