AT_arc150_e [ARC150E] Weathercock

[problemUrl]: https://atcoder.jp/contests/arc150/tasks/arc150_e $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ S $

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

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ K\ \leq\ 2\ \times\ 10^5 $ - $ S $ は `L`,`R` のみからなる長さ $ N $ の文字列 - 入力される数値はすべて整数 ### Sample Explanation 1 各時刻において $ 7 $ 人が向いている方向を文字列で表すと $ t=1 $ では `LLRLRRL` 、$ t=2 $ では `LLRLRLL` 、 $ t=3 $ では `LLLLLLL` となります。 時刻 $ t=3 $ 以降では $ 7 $ 人が向いている方向は変化しません。よって答えは $ 1+1+2+1+2+2+0=9 $ になります。