まず、 \(R, P, S\) を \(0, 1, 2\) に変換します。

そして、長さ \(N\) のジャンケン文字列 \(S\) を、以下の条件を満たす長さ \(N-1\) の数列 \(S'\) で表します。

• $1 \le i \le N-1$ に対して $S'_i \in \{-1, 0, 1\}$
• $S_i + S'_i = S_{i+1}$

\(S\) をジャンケンマシーンに入れて得られる文字列を \(T\) として、\(T'\) も同様に定義します。\(S'\) と \(T'\) を比較して観察すると、以下の重要な事実を得ます。

[事実] \(S'\) に現れる全ての \(-1\) をそれぞれ \(1\) つ左に移動させ（このとき、\(1\) と場所が重なったものについては \(0\) に置き換える）、一番右の文字を削除することで \(T'\) が得られる。

さて、\(k\) 回の操作をまとめて逆向きに行うことを考えましょう。\(-1\) の要素を全て \(k\) ずつ右に移動させます。この際に既存の \(1\) と交差するようなことがあれば、問題の答えは \(0\) です。

あとは、\(-1\) と \(1\) の間の各区間について、「\(k\) 回の操作をした後、全ての \(1\) と \(-1\) が打ち消し合うように数字を埋める場合の数」を求め、それらを掛け合わせれば良いです。

この場合の数は、以下のようなDPで計算できます。

\(dp[N]\) を、「長さ \(N\) の区間についての答え」と定義すると、区間の一番左に \(0\) を書き込む場合と \(1\) を書き込む場合に場合分けをすると、以下のような漸化式が成り立ちます。

// 一番左に 0 を書き込んだ場合
dp[i] += dp[i - 1];

// 一番左に 1 を書き込んだ場合
for (int j = 0; j <= min(i - 2, k - 1); j++) {
   dp[i] += dp[j] * dp[i - j - 2];
}

なお、数列の両端の部分や、\(S'\) が \(1\) 種類の文字からなる場合には少し違う漸化式になり、例外処理が必要です。

bonus : \(N, k \le 10^5\) の場合の解法も考えてみてください。