C. [2026 CCPC_NC_I C] 简单字符串题

    Type: Default 4000ms 1024MiB

[2026 CCPC_NC_I C] 简单字符串题

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

并递归地定义 A1=AA^1=A,An=An−1AA^n=A^{n-1}A (n≥2n\ge 2 且为正整数)。例如 A=abbA=\texttt{abb},则 A3=abbabbabbA^3=\texttt{abbabbabb}。

现给定一个长度为 nn 的字符串 SS,给定常数 kk,求 S=AiB1B2…BkCjS=A^iB_1B_2 \ldots B_kC^j 的方案数,其中 A,B1,B2,…,Bk,CA,B_1,B_2,\ldots,B_k,C 为任意非空字符串,i,ji,j 为任意正整数。

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

答案要对 998244353998244353 取模。

Format

Input

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

Output

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

Samples

5 1
aabcc
11
6 2
aaaaaa
19
8 1
aabaabcd
27

Note

对于第一组样例,有以下 1111 种方案:

  • $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$