题目描述

小魔女茜塔制造了 $n$ 条时间线。第 $i$ 条时间线中有一个箱子和一只猫，字符串 $S$ 描述每只猫当前的状态：

• 0：第 $i$ 只猫是活的；
• 1：第 $i$ 只猫是死的；
• ?：第 $i$ 只猫处于生死叠加态。

茜塔希望最终让所有猫都活着。一次完整方案按如下方式进行：

1. 首先观测所有 ?，并分别确定它们最终是 0 还是 1。这一步不计入操作次数。
2. 之后可以反复执行：选择一只当前已经死亡的猫 $i$，将它救活；同时编号 $1,2,\ldots,i-1$ 的所有猫状态全部反转，即活变死、死变活。该操作计为一步。
3. 当所有猫都活着时方案结束。

给定步数上限 $m$，求一共有多少种不同方案能在不超过 $m$ 步内使所有猫都活着。

两种方案不同，当且仅当：

• 对某个 ? 的观测结果不同；或
• 之后至少有一步选择救活的猫编号不同。

答案对 $998244353$ 取模。

输入格式

第一行包含两个正整数 $n,m$。

第二行包含一个长度为 $n$ 的字符串 $S$，其中每个字符均为 0、1 或 ?。

输出格式

输出一个整数，表示合法方案数对 $998244353$ 取模后的结果。

输入输出样例 #1

输入

3 5
111

输出

6

输入输出样例 #2

输入

8 114
????????

输出

962557607

输入输出样例 #3

输入

10 50
10?01?0??1

输出

600070890

样例说明

对于样例 #1，不需要进行观测。可行操作序列共有 $7$ 种，其中长度不超过 $5$ 的有 $6$ 种，因此答案为 $6$。

数据范围与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1\le n\times m\le4.9\times10^6$。

请注意程序常数对运行时间的影响。