题目描述
Problem Description
A "JANKEN string" is a string consisting only of the characters R, S, and P. A "JANKEN machine" is a device that takes a JANKEN string as input and outputs another JANKEN string that is one character shorter. The behavior of the machine is defined as follows:
- Let the input string be $ S $ and the output string be $ T $. For each $ i $th character of $ S $ (denoted as $ S_i $) and $ (i+1) $th character of $ S $ (denoted as $ S_{i+1} $), the $ i $th character of $ T $ (denoted as $ T_i $) is determined by the function $ f(S_i, S_{i+1}) $ for $1 \leq i \leq |S|-1$. The function $ f $ outputs according to the following table: (Intuitively, it is the hand that would not lose in a rock-paper-scissors game between two people.)
| $ 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}$ |
An integer $ k $ and a JANKEN string $ S $ are given. There are $ 3^{k+|S|} $ JANKEN strings of length $ k + |S| $. Among these, find the number of strings that can produce $ S $ after $ k $ iterations of the JANKEN machine, modulo $ 998244353 $.
Input Format
The input is given from the standard input in the following format:
$ S $ $ k $
Output Format
Output the answer in one line.
Sample Input and Output
Sample Input #1
SSRP
1
Sample Output #1
3
Sample Input #2
SSPPP
3
Sample Output #2
88
Sample Input #3
RRRPPP
20
Sample Output #3
88454144
Notes/Hints
Constraints
- $1 \leq |S| \leq 3000$
- $1 \leq k \leq 3000$
- $ S $ consists of
R,S, andP.
Sample Explanation 1
There are $ 3 $ ways: SSSRP, SPSRP, PSSRP.
Sample Explanation 3
Output the answer modulo $ 998244353 $.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分
样例输入
SSRP
1
样例输出
3