拉美西斯二世在战斗中凯旋归来。为了纪念他的胜利，他决定建造一座宏伟的花园。花园将包含一条从他位于卢克索的宫殿一直延伸到卡纳克神庙的长长的植物线。它将仅由莲花和纸莎草组成，因为它们分别象征着上埃及和下埃及。

花园必须恰好包含 $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 1,000,000$ $7 \le M \le 10,000,000$

子任务

在总分 40 分的测试点中，$N$ 不超过 40。

输入格式

程序必须从标准输入读取以下数据： 第 1 行包含整数 $N$，即花园中的植物数量。 第 2 行包含整数 $M$。 * 第 3 行包含一个长度为 $N$ 的字符串，由 'L'（莲花）或 'P'（纸莎草）组成，代表一个平衡花园。

输出格式

程序必须向标准输出写入一行，包含一个介于 0 和 $M-1$（含）之间的整数，即输入中描述的花园的编号对 $M$ 取模后的结果。

样例

样例输入 1

5
7
PLPPL

样例输出 1

5

说明 1

PLPPL 的实际编号是 12。因此，输出是 12 对 7 取模，即 5。

样例输入 2

12
10000
LPLLPLPPLPLL

样例输出 2

39