题目描述

有$NK$个人从左到右站在一条直线上，我们用从左到右的顺序来表示他们，将第$i$个人$(0 \leq i \leq NK-1)$表示为左到右的序列。

每个人总是面向左或者右。在$t=0$时刻，每个人的方向由长度为$N$的字符串$S=S_0 S_1 \dots S_{N-1}$表示，其中$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

如果我们表示每个时刻七个人的方向，$t=1$时为LLRLRRL，$t=2$时为LLRLRLL，$t=3$时为LLLLLLL。

在$t=3$之后，七个人的方向不再改变。因此，答案是$1+1+2+1+2+2+0=9$。

示例输入 2

4 10
LLRR

示例输出 2

0

示例输入 3

23 200
RLRRRLLLLLLLLRRRLLRLRRR

示例输出 3

2207