时间限制：2 秒；空间限制：256 MB。

$hyx$ 又双叒叕在 $NOI$ 模拟赛得到“正确”的题意。

让我们来到事发现场：

给一个由 RSP 这三种字母组成的字符串 $S$，其中 RSP 分别表示石头、剪刀和布。我们要进行 $k$ 轮运算。

每一轮，我们会将 $S$ 中相邻两个字符进行比较，并且保留能够获胜的那个手势（如果平局，那么任意保留一个）。这样就能得到一个长度为 $|S|-1$ 的字符串。

现在给定一个整数 $k$ 和一个字符串 $S$，求以下问题的答案：

长度为 $k+|S|$ 的剪刀石头布字符串共有 $3^{k+|S|}$ 种可能性。在这些字符串中，有多少字符串经过 $k$ 轮运算后，会输出字符串 $S$？

于是他根据他的理解出了一道新题。

题目描述

给一个由 RSP 这三种字母组成的字符串 $S$，其中 RSP 分别表示石头、剪刀和布。我们要进行 $k$ 轮运算。

每一次，我们会将 $S$ 中相邻两个字符进行比较，并且保留能够获胜的那个手势（如果平局，那么任意保留一个）。这样就能得到一个长度为 $|S|-1$ 的字符串。

现在给定一个整数 $k$ 和一个字符串 $S$，求以下问题的答案：

长度为 $k+|S|$ 的剪刀石头布字符串共有 $3^{k+|S|}$ 种可能性。在这些字符串中，有多少字符串经过 $k$ 次比较后，可以得到字符串 $S$？

输出答案对 $P$ 取模的结果。$P$ 不一定是质数。

$|S|\le200$，$K\le3000$。

相信大家都看出了两道题目的区别，原题每一轮同时将每一对相邻位置进行比较，每对的结果作为下一轮的字符串，而本题是任选一对比较，新串是在原串基础上删掉一个字符而得。

输入格式

第一行一个字符串 $S$。

第二行两个数 $k,P$。

输出格式

输出 $K$ 行，每行一个数，第 $i$ 行表示 $k=i$ 时答案模 $P$ 的值。

转换注：原文在输入格式中使用小写 $k$，输出格式中使用大写 $K$；此外，两个样例都仅给出一行输出，与“输出 $K$ 行”的要求不一致。此处均保留原文，未擅自修改输出要求或补充样例答案。

样例 1 输入

RR
2 20

样例 1 输出

17

样例 2 输入

SSPPPSS
7 998244353

样例 2 输出

291335

数据范围

令 $n=|S|$。

对于所有数据，$1\le n\le200$，$1\le k\le3000$，$2\le P\le10^9$。

部分分如下，表中未填表示没有特别的限制，数据范围包含的有子任务依赖。