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 组成。