B - JANKEN Machine Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

「ジャンケン文字列」とは、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 で割った余りを出力してください。