分数: 800 点
问题陈述
NK 人们从左到右站成一排。让我们将他们表示为人 i (0\leq i \leq NK-1) 从左到右。
每个人始终面向左或右。每个人当时的方向 t=0 用长度的字符串表示 N, S=S_0 S_1 \dots S_{N-1},包括 L 和 R。时 t=0, 人 i 面向左,如果 S_{i \bmod N} is L,如果是,则正确 R.
时间 t=0.5,\ 1.5,\ 2.5 ,\ \dots,这些人 同时 根据以下规则改变方向。
- 当一个人面向左时:
如果该人所面向的方向有一个或多个人,并且其中一半以上的人面向右侧,则该人会改变方向并面向右侧。否则,该人不会改变方向。 - 当一个人面朝右侧时:
如果该人所面对的方向有一个或多个人,并且其中一半以上的人面向左,则该人会改变方向并面向左。否则,该人不会改变方向。
求总和,模 998244353,次数 NK 人们会随着时间改变方向 t=0 to t=10^{100}.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 2 \times 10^5
- S 是一个长度为 N 组成
L和R. - 输入中的所有数值均为整数。
输入
输入由标准输入按以下格式给出:
N K S
输出
打印答案。
示例输入 1
7 1 RRLRLLL
示例输出 1
9
如果我们代表七个人每次的方向,我们有 LLRLRRL at t=1, LLRLRLL at t=2,和 LLLLLLL at t=3.
之后 黑板上写着 t=3,七人的方向没有改变。因此,答案是 1+1+2+1+2+2+0=9.
示例输入 2
4 10 LLRR
示例输出 2
0
示例输入 3
23 200 RLRRRLLLLLLLLRRRLLRLRRR
示例输出 3
2207