题目描述

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

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

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

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

输入格式

第一行两个正整数 $n,k$。

第二行一个长为 $n$ 的字符串 $s$。

输出格式

一行一个正整数，表示所有轮中每个人的转头次数之和对 $998244353$ 取模的结果。

样例 1

输入

7 1
RRLRLLL

输出

9

样例 2

输入

4 10
LLRR

输出

0

样例 3

输入

23 200
RLRRRLLLLLLLLRRRLLRLRRR

输出

2207

说明/提示

对于所有数据，$1\le n,k\le 2\times 10^5$，$s$ 是一个长度为 $n$ 且仅包含字符 L 和 R 的字符串。