AT_utpc2020_b JANKEN Machine

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_b 「ジャンケン文字列」とは、`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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ k $

答えを $ 1 $ 行に出力せよ。

### 制約 - $ 1\ \leq\ |S|\ \leq\ 3000 $ - $ 1\ \leq\ k\ \leq\ 3000 $ - $ S $ は `R`, `S`, `P` からなる ### Sample Explanation 1 `SSSRP` , `SPSRP` , `PSSRP` の $ 3 $ 通りです。 ### Sample Explanation 3 $ 998244353 $ で割った余りを出力してください。