题目描述Description

沉迷《黑神话悟空》的小W在发售前沉迷赛博金石学，现在他在研究某一帧宣传片中的经文，这个经文是一个包含 \(n\) 个字符的字符串,现在小W尝试破译一个词的意思，这个词为经文的一个子串\(s\)。小W又精通数学，因此他想到一个问题，求一段长度为 \(n\) 的经文，包含恰好 \(k\) 个 不重叠的\(s\) 的合法方案会有多少种，答案对 \(998244353\) 取模。

不重叠是指没有共用字符，例如 \(s=\)aba，则 ababa 中只有一个不重叠的 \(s\)，而 abaaba, abacaba 中均有两个不重叠的 \(s\)。

输入格式Input

第一行输入两个正整数 \(n,k\) \((1 \le n \le 10^4, 1 \le k \le 10)\).

第二行输入一个字符串 \(s\) \((1 \le \|s\| \le 100)\).

注意：题目中字符串仅包含小写字母’a’-‘z’。

输出格式Output

输出一个整数表示答案。

样例Sample

来源Source