该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

我们可以定义 $AB$ 表示两个字符串 $A,B$ 相连接，例如 $A=\texttt{aab}$，$B=\texttt{ab}$，则 $AB=\texttt{aabab}$。

并递归地定义 $A^1=A$，$A^n=A^{n-1}A$ ($n\ge 2$ 且为正整数)。例如 $A=\texttt{abb}$，则 $A^3=\texttt{abbabbabb}$。

现给定一个长度为 $n$ 的字符串 $S$，给定常数 $k$，求 $S=A^iB_1B_2 \ldots B_kC^j$ 的方案数，其中 $A,B_1,B_2,\ldots,B_k,C$ 为任意非空字符串，$i,j$ 为任意正整数。

两种方案不同当且仅当 $A,B_1,B_2,\ldots,B_k,C,i,j$ 中有至少一个字符串或数字不同。

答案要对 $998244353$ 取模。

Format

Input

第一行两个整数 $n,k$ ($2\le n\le 5\times 10^5$, $0\le k\le n-2$)，第二行一个字符串 $S$，意义见题目描述。$S$ 仅由英文小写字母构成。

Output

输出一行一个整数表示答案。

Samples

5 1
aabcc

11

6 2
aaaaaa

19

8 1
aabaabcd

27

Note

对于第一组样例，有以下 $11$ 种方案：

• $A=\texttt{a},\ B_1=\texttt{a},\ C=\texttt{bcc},\ i=1,\ j=1$
• $A=\texttt{a},\ B_1=\texttt{ab},\ C=\texttt{cc},\ i=1,\ j=1$
• $A=\texttt{a},\ B_1=\texttt{abc},\ C=\texttt{c},\ i=1,\ j=1$
• $A=\texttt{aa},\ B_1=\texttt{b},\ C=\texttt{cc},\ i=1,\ j=1$
• $A=\texttt{aa},\ B_1=\texttt{bc},\ C=\texttt{c},\ i=1,\ j=1$
• $A=\texttt{aab},\ B_1=\texttt{c},\ C=\texttt{c},\ i=1,\ j=1$
• $A=\texttt{a},\ B_1=\texttt{ab},\ C=\texttt{c},\ i=1,\ j=2$
• $A=\texttt{a},\ B_1=\texttt{b},\ C=\texttt{c},\ i=2,\ j=2$
• $A=\texttt{aa},\ B_1=\texttt{b},\ C=\texttt{c},\ i=1,\ j=2$
• $A=\texttt{a},\ B_1=\texttt{b},\ C=\texttt{cc},\ i=2,\ j=1$
• $A=\texttt{a},\ B_1=\texttt{bc},\ C=\texttt{c},\ i=2,\ j=1$