Problem Description

Given a string $S$ of length $N$, the string consists only of the characters $0$, $1$, and $\#$.

You may perform the “compress” operation on string $S$ any number of times (including $0$ times). One compress operation is defined as follows: choose two adjacent characters in the string, and both of them are not $\#$. Delete either one of them. The remaining characters will automatically be concatenated together.

Now a target length $K$ is given. Please compute: after performing some operations, how many different strings of length exactly $K$ can be obtained in the end. Since the answer may be very large, output the number of ways modulo $998244353$.

Input Format

The first line contains two integers $N$ and $K$, representing the initial length of the string and the target length.

The second line contains a string $S$ of length $N$ consisting only of $0$, $1$, and $\#$.

Output Format

Output one integer, the number of different strings that can be obtained modulo $998244353$.

6 4
010#11

5

Hint

Sample Explanation

The different strings that can be obtained are:

• 00#1
• 01#1
• 10#1
• 0#11
• 1#11

There are $5$ kinds in total.

Constraints

For $20\%$ of the testdata, $1 \le N \le 200$, and the number of $\#$ characters in $S$ does not exceed $1$.

For all testdata, $1 \le N \le 10^5$, $1 \le K \le 2026$, and $K \le N$, and the number of $\#$ characters in $S$ does not exceed $100$.

Translated by ChatGPT 5