AT_utpc2020_b JANKEN Machine
题目描述
$S$ 是一个仅由 `R`,`P`,`S` 组成的字符串。定义“对 $S$ 进行一次变换操作”如下：
- 令输出字符串为 $T$。$|T|=|S|-1$，且对于任意 $i\in [1,n) \cap \Z$，$T_i=f(S_i,S_{i+1})$。
其中，函数 $f(x,y)$ 的值如下表所示：
| | `R` | `S` | `P` |
| :----------: | :----------: | :----------: | :----------: |
| `R` | `R` | `R` | `P` |
| `S` | `R` | `S` | `S` |
| `P` | `P` | `S` | `P` |
有一个字符串经过 $k$ 次变换得到了字符串 $S$。给定整数 $k$ 和字符串 $S$，请求出有多少个字符串满足此条件？答案模 $998244353$。（长为 $k+|S|$ 的，仅由 `R`,`P`,`S` 组成的字符串有 $3^{k+|S|}$ 个。）
输入格式
共两行，第一行为一个字符串 $S$，第二行为一个整数 $k$。
输出格式
一行一个数表示答案。
说明/提示
#### 样例 #1 解释
满足条件的字符串分别为 `SSSRP`，`SPSRP`，`PSSRP`。
#### 样例 #3 解释
请将答案对 $998,244,353$ 取模。
#### 数据规模与约定
对于全部测试点，保证 $1\le |S|,k\le 3000$，$S$ 仅由 `R`,`P`,`S` 组成。