考虑一个长度为 $N$ 的字符串。令字符串 $S$ 为该字符串重复 $K$ 次后的结果。你对这个字符串的“WAC程度”很感兴趣，因此你的任务是求出该字符串的 WAC-ness。

一个字符串的 WAC-ness 定义为 “WAC” 作为该字符串的子序列出现的次数。

子序列是指从给定序列中删除零个或多个字符，而不改变剩余字符顺序所得到的字符串。如果两个子序列所使用的原始字符串下标集合至少有一个不同，则它们被视为不同的子序列。例如，在字符串 “AABC” 中，由下标 1, 3, 4 构成的子序列与由下标 2, 3, 4 构成的子序列是不同的。

由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含两个整数 $N$ 和 $K$ ($1 \le N \le 200\,000, 1 \le K \le 200\,000$)，分别表示原始字符串的长度以及该字符串重复形成 $S$ 的次数。第二行（也是最后一行）包含长度为 $N$ 的原始字符串，由大写英文字母组成。

输出格式

输出字符串 $S$ 的 WAC-ness 对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

5 1
WABCA

样例输出 1

1

样例输入 2

5 2
WABCA

样例输出 2

5