E - Weathercock Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

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

入力例 1

7 1
RRLRLLL

出力例 1

9

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

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

入力例 2

4 10
LLRR

出力例 2

0

入力例 3

23 200
RLRRRLLLLLLLLRRRLLRLRRR

出力例 3

2207

Score : 800 points

Problem Statement

NK people are standing in a line from left to right. Let us denote them as person i (0\leq i \leq NK-1) from left to right.

Each person is always facing either left or right. The direction of each person at time t=0 is represented by a string of length N, S=S_0 S_1 \dots S_{N-1}, consisting of L and R. At time t=0, person i is facing left if S_{i \bmod N} is L, and right if it is R.

At time t=0.5,\ 1.5,\ 2.5 ,\ \dots, these people simultaneously change their directions according to the following rules.

  • When a person is facing left:
    If there are one or more people in the direction the person is facing, and more than half of those people are facing right, the person changes direction and faces right. Otherwise, the person does not change direction.
  • When a person is facing right:
    If there are one or more people in the direction the person is facing, and more than half of those people are facing left, the person changes direction and faces left. Otherwise, the person does not change direction.

Find the sum, modulo 998244353, of the numbers of times the NK people change direction from time t=0 to t=10^{100}.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • S is a string of length N consisting of L and R.
  • All numerical values in the input are integers.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer.

Sample Input 1

7 1
RRLRLLL

Sample Output 1

9

If we represent the directions of the seven people at each time, we have LLRLRRL at t=1, LLRLRLL at t=2, and LLLLLLL at t=3.

After t=3, the directions of the seven people do not change. Therefore, the answer is 1+1+2+1+2+2+0=9.

Sample Input 2

4 10
LLRR

Sample Output 2

0

Sample Input 3

23 200
RLRRRLLLLLLLLRRRLLRLRRR

Sample Output 3

2207