#P17760. 机拳猜

机拳猜

题面描述

小 hh 又双叒叕在 NOINOI 模拟赛得到“正确”的题意。

让我们来到事发现场:

给一个由 RSP\texttt{RSP} 这三种字母组成的字符串 SS,其中 RSP\texttt{RSP} 分别表示石头,剪刀和布。我们要进行 kk 轮运算。

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

现在给定一个整数 kk 和一个字符串 SS,求以下问题的答案:

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

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

题目描述

给一个由 RSP\texttt{RSP} 这三种字母组成的字符串 SS,其中 RSP\texttt{RSP} 分别表示石头,剪刀和布。我们要进行 kk 轮运算。

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

现在给定一个整数 kk 和一个字符串 SS,求以下问题的答案:

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

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

∣S∣≤200|S| \le 200 , k≤3000k \le 3000

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

输入格式

第一行一个字符串 SS。

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

输出格式

输出一个数表示答案。

样例输入 #1

RR
2 20

样例输出 #1

17

样例输入 #2

SSPPPSS
7 998244353

样例输出 #2

291335

数据范围

令 n=∣S∣n=|S|。

对于所有数据,1≤n≤2001\le n \le 200,1≤k≤30001\le k \le 3000,2≤P≤1092\le P \le 10^9。

部分分如下,表中未填表示没有特别的限制。

子任务 分值 n≤n\le k≤k\le 特殊性质
1 5 66 77
2 88 99
3 1010 1111
4 11
5 22
6 11
7 22
8 SS 为 RSP\texttt{RSP} 的循环
9 10 SS 只由 RR 构成
10 8080
11 500500 P=998244353P=998244353
12
13 P=998244353P=998244353
14