9026: Bobo String Count

After the failure of “Bobo Encoding” (for information on “Bobo Encoding”, you may refer to the statement of “Binary String Construction”, but it is not necessary to understand this problem), Bobo decided to study strings carefully. Now he is considering a very simple problem:

Given a string $t$ consisting of only $0$s and $1$s,  a positive integer $n$, and an integer 0≤k≤n, you need to calculate the number of strings $s$ consisting of only $0$s and $1$s with length exactly $n$, satisfying:

•  The string $t$ appears exactly $k$ times in the string $s$ (note that the appearance here can be overlapped, such as 101 appearing twice in 10101).

Since the answer may be too large, you need to output the answer modulo $998244353$.

The first line contains two integers n,k (1≤n≤50000,0≤k≤n). 
The second line contains a binary string $t$ (1≤∣t∣≤50000).

Output an integer in one line, denoting the answer modulo $998244353$.

第三组输入输出：
输入
10 0
1001
输出
631