← 返回题目列表

AtCoder · utpc2020_b

B. JANKEN 机器

中文机器翻译题面 查看原题

問題文

什么是“石头、剪刀、布”? 仅由R , S , P 的 3 类型的字符组成的字符串。
“石头剪刀布机”是一种接收石头剪刀布字符串作为输入并计算长度的机器。 1 这是一个输出另一个石头剪刀布小串的设备。设备的行为定义如下。

  • 输入输入字符串 S ,输出字符串 T 。S 的 i 第一个字母 如果我们将其表示为 S_i、T 的 i 第一个字母 如果我们将其表示为 T_i , 变为T_i = f(S_i, S_{i+1}) (1 \le i \le |S|-1)的字符串 输出 T 。在这里发挥作用 f 的输出对应于下表。 (直观地说,2 和别人玩石头剪刀布的时候,不会输的那个。 )
f(x, y) y=\mathrm{R} y=\mathrm{S} y=\mathrm{P}
x=\mathrm{R} \mathrm{R} \mathrm{R} \mathrm{P}
x=\mathrm{S} \mathrm{R} \mathrm{S} \mathrm{S}
x=\mathrm{P} \mathrm{P} \mathrm{S} \mathrm{P}

整数 k 和石头、剪子、布串 给出 S 。长度 k + |S| 石头剪刀布字符串是 其中有 3^{k+|S|} 个,但其中石头剪刀布机的输入是 通过重复 k 次 求出可以得到 S 的事物的数量。 可以表示为 998244353 的余数。

制約

  • 1 \leq |S| \leq 3000
  • 1 \leq k \leq 3000
  • S 是 给出了 R, S, P 组成的

入力

输入是按以下格式从标准输入给出的。

S
k

出力

答案 输出为 1 行输出。 由于字符串以


入力例 1

SSRP
1

出力例 1

3

SSSRP , SPSRP , PSSRP 的 3 没错。 不要忘记除以


入力例 2

SSPPP
3

出力例 2

88

入力例 3

RRRPPP
20

出力例 3

88454144

998244353 后的余数。