题目描述

$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$

输出格式

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

题目大意

有 $n\times k$ 个人排成一行，从左往右按 $0,1,\cdots nk-1$ 编号。每个人初始都面对着一个方向 L 或 R。给出一个字符串 $s_{0\cdots n-1}$，则第 $i$ 个人的方向为 $s_{i \bmod n}$。

接下来进行若干轮操作，每一轮所有人 同时进行如下操作：

1. 若当前某人面对左边，且他左边的人中面对右边的人数超过一半，则他转头面向右边。
2. 若当前某人面对右边，且他右边的人中面对左边的人数超过一半，则他转头面向左边。

操作进行 $10^{100}$ 轮，请求出所有轮中每个人转头的次数之和。$n,k\le 2\times 10^5$。

7 1
RRLRLLL

9

4 10
LLRR

0

23 200
RLRRRLLLLLLLLRRRLLRLRRR

2207

提示

制約

• $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$ になります。