配点 : $800$ 点

問題文

$NK$ 人の人が横一列に並んでいます。左から順に人 $i\ (0\leq i \leq NK-1)$ と表記します。

各人は常に左右どちらかの方向を向いています。時刻 $t=0$ において各人がどちらを向いているかは、L,R のみからなる長さ $N$ の文字列 $S=S_0 S_1 \dots S_{N-1}$ で表されます。時刻 $t=0$ において人 $i$ は $S_{i \bmod N}$ が L のとき左を、 R のとき右を向いています。

これらの人は時刻 $t=0.5,\ 1.5,\ 2.5 ,\ \dots$ において以下の規則に従って向いている方向を同時に変化させます。

• その時点で左を向いている場合 自分が向いている方向に人が存在し、その中で過半数の人が右を向いている場合、向いている方向を右に変える。そうでない場合向いている方向を変えない。
• その時点で右を向いている場合 自分が向いている方向に人が存在し、その中で過半数の人が左を向いている場合、向いている方向を左に変える。そうでない場合向いている方向を変えない。

時刻 $t=0$ から $t=10^{100}$ までの間に、$NK$ 人それぞれが向いている方向を変える回数の総和を $998244353$ で割った余りを求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 2 \times 10^5$
• $S$ は L,R のみからなる長さ $N$ の文字列
• 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $K$

$S$

出力

答えを出力してください。

7 1
RRLRLLL

9

各時刻において $7$ 人が向いている方向を文字列で表すと $t=1$ では LLRLRRL 、$t=2$ では LLRLRLL 、 $t=3$ では LLLLLLL となります。

時刻 $t=3$ 以降では $7$ 人が向いている方向は変化しません。よって答えは $1+1+2+1+2+2+0=9$ になります。

4 10
LLRR

0

23 200
RLRRRLLLLLLLLRRRLLRLRRR

2207