Задача №3305. Linear Garden
Рамзес Второй только что вернулся с победоносной битвы. Чтобы увековечить свою победу, он
решил построить величественный сад. Сад будет содержать длинную линию из растений, которая
будет тянуться вдоль всего пути от его дворца в Луксоре до Карнакского храма. Сад будет состоять
только из лотосов и папирусов, поскольку они символизируют Верхний и Нижний Египет
соответственно.
Сад должен содержать ровно \(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\) не имеет никакого другого смысла, кроме как упрощения вычислений.
\(7 \le M \le 10000000\)
•Строка 1 содержит целое число \(N\) – количество растений в саду.
•Строка 2 содержит целое число \(M\).
•Строка 3 содержит строку из \(N\) символов ‘L’ (лотос) и ‘P’ (папирус), которая представляет сбалансированный сад.
Сад должен содержать ровно \(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 \le N \le 1000000\)\(7 \le M \le 10000000\)
Входные данные
Ваша программа должна читать из стандартного ввода данные в следующем формате:•Строка 1 содержит целое число \(N\) – количество растений в саду.
•Строка 2 содержит целое число \(M\).
•Строка 3 содержит строку из \(N\) символов ‘L’ (лотос) и ‘P’ (папирус), которая представляет сбалансированный сад.
Выходные данные
Ваша программа должна вывести в стандартный вывод единственную строку, содержащую одно целое число от 0 до \(M-1\) включительно – номер, присвоенный саду, описанному в стандартном вводе, вычисленный по модулю M.
Оценивание
Для некоторых тестов, в сумме оцениваемых в 40 баллов, \(N\) не будет превышать 40.
Примечание к первому примеру
Фактический номер, присвоенный PLPPL, это 12. Ответ равен 5, то есть, 12 по модулю 7.
Примеры
Входные данные
5 7 PLPPL
Выходные данные
5
Входные данные
12 10000 LPLLPLPPLPLL
Выходные данные
39
Сдать: для сдачи задач необходимо войти в систему