题目描述

考虑有如下字符串匹配问题：

• 给定长度为 $m$ 的字符串 $T$ 和长度为 $n$ 的字符串 $S$，对于每一个 $i\in[1,n]$，求出最大的自然数 $j$，使得 $j\le\min(m,i)$ 且 $S[i-j+1,i]=T[1,j]$，将此 $j$ 称为 $f_i$。

其中 $S[i,j]$ 表示从 $S_i$ 到 $S_j$ 的 $S$ 的子串，若 $i>j$ 则表示空串。

考虑如下算法：

• 维护一个变量 $cur$，初始 $cur=0$；
• 依次枚举 $i=1,\ldots,n$；
• 若 $cur<m$ 且 $S_i=T_{cur+1}$，则 $cur\leftarrow cur+1$，否则 $cur\leftarrow0$；
• 令 $f_i\leftarrow cur$。

可以用如下伪代码来描述这个算法：

procedure MATCH(n, m, s, t)
    i ← 1
    cur ← 0
    while i ≤ n do
        if cur < m And s[i] = t[cur + 1] then
            cur ← cur + 1
        else
            cur ← 0
        end if
        f[i] ← cur
    end while
    return f
end procedure

你一定会发现这个算法是错误的，例如当 $S=\texttt{aaab}$，$T=\texttt{aab}$ 时，正确的 $f$ 数组为 $[1,2,2,3]$，而该算法得到的 $f$ 数组为 $[1,2,0,0]$。

请求出对于给定的 $S$，该算法的正确率，具体来说：

• 给定一个长度为 $n$ 的字符串 $S$ 和一个整数 $m$，若随机选取一个长度为 $m$ 的字符串 $T$（即每一位出现每种字母概率均等），按照如上错误算法算出的每个 $f_i$ 都与正确的 $f_i$ 一致的概率，答案对 $998244353$ 取模。

注意：$S,T$ 的字符集均为 $\{\texttt{a},\texttt{b},\texttt{c},\texttt{d},\texttt{e}\}$，即给定的 $S$ 只包含这些字符，$T$ 等概率取由这些字符组成的字符串。

输入格式

第一行两个整数 $n,m$，分别表示 $S$ 的长度和 $T$ 的长度。

第二行，一个长度为 $n$、字符集为 $\{\texttt{a},\texttt{b},\texttt{c},\texttt{d},\texttt{e}\}$ 的字符串 $S$。

输出格式

输出一行，一个整数，表示算法正确概率对 $998244353$ 取模的结果。

样例输入

3 2
aba

样例输出

678806161

样例解释

当 $T=\texttt{ab}$ 时，正确的 $f_3=1$ 和该算法得到的 $f_3=0$ 不同。对于其余的 $T$，该算法均能得到正确的结果，所以有 $5^2-1=24$ 种 $T$ 使得该算法正确，所以输出

$\frac{24}{25}\bmod 998244353=678806161$。

数据范围

对于 $100\%$ 的数据满足：$1\le n,m\le2000$，$S$ 的字符集为 $\{\texttt{a},\texttt{b},\texttt{c},\texttt{d},\texttt{e}\}$。

• 对于 $15\%$ 的数据：$1\le n,m\le8$。
• 对于 $45\%$ 的数据：$1\le n,m\le100$。
• 对于另外 $15\%$ 的数据：$1\le n,m\le16$，且 $S$ 的字符集为 $\{\texttt{a},\texttt{b}\}$（这并不代表 $T$ 的字符集也是 $\{\texttt{a},\texttt{b}\}$）。