题目描述

给定一个长度为 $N$ 的字符串 $S$，字符串仅由字符 $0$、$1$ 和 $\#$ 组成。

你可以对字符串 $S$ 进行任意次（包括 $0$ 次）“压缩”操作。一次压缩操作的定义如下：选择字符串中两个相邻且均不为 $\#$ 的字符，删除其中的任意一个。剩余部分的字符将自动拼接在一起。

现给定一个目标长度 $K$。请计算：在进行若干次操作后，最终能够得到多少种不同的、长度恰好为 $K$ 的字符串。由于答案可能很大，请输出方案数对 $998244353$ 取模后的结果。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示初始字符串的长度和目标长度。

第二行包含一个长度为 $N$ 且仅由字符 $0$、$1$、$\#$ 组成的字符串 $S$。

输出格式

输出一个整数，表示能够得到的不同字符串的数量对 $998244353$ 取模后的值。

6 4
010#11

5

提示

【样例说明】

能够得到的不同字符串为：

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

共 $5$ 种。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \le N \le 200$，字符串 $S$ 中字符 $\#$ 的数量不超过 $1$；

对于所有评测用例，$1 \le N \le 10^5$，$1 \le K \le 2026$，且 $K \le N$，字符串 $S$ 中字符 $\#$ 的数量不超过 $100$。