P16812 [Lanquiao Cup 2026 National Python A] Compress String

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

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 one integer, the number of different strings that can be obtained modulo $998244353$.

### 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