小重和小庆正在下“兵棋”。

$n$ 个士兵棋子排成一行，每个士兵要么是小重的要么是小庆的。接下来有若干天，每天如果第 $i$ 个士兵和第 $i+1$ 只士兵不属于同一玩家，那么第 $i$ 只士兵会击杀第 $i+1$ 只士兵。所有击杀操作会同时进行，士兵被击杀后会被移除。例如，如果某一天第 3 个士兵击杀第 4 个士兵，第 4 个士兵击杀第 5 个士兵，那么结果就是第 4 个和第 5 个士兵都会被移除。

现在小重和小庆已经在一些位置上摆好自己的士兵了，但他们还没确认其余位置摆什么士兵。你需要对于所有方案，求出 $k$ 天后剩下的士兵数的总和，答案对 $998244353$ 取模。

简要题意

对于一个 $01$ 字符串，定义其权值如下：执行 $k$ 轮操作，每次找到所有 $s_{i}\neq s_{i-1} (i\ge 2)$ 的位置 $i$，并把 $s_i$ 删掉。它的权值就是最后剩余的字符数。

现在字符串中有一些问号，这些位置既可以填 $0$ 也可以填 $1$。你需要对于所有填数方案求权值总和。答案对 $998244353$ 取模。

输入格式

第一行输入两个正整数 $n,k$。

第二行包含一个字符串 $s$。$s_i=\texttt{0}$ 表示第 $i$ 个位置上摆了小重的士兵，$s_i=\texttt{1}$ 表示第 $i$ 个位置摆了小庆的士兵，$s_i=\texttt{?}$ 表示第 $i$ 个位置还没摆士兵。

输出格式

共一行，用一个正整数表示答案。

样例一

input

5 1
01?10

output

4

样例二

input

6 2
?????0

output

89

样例三$\sim$九

见附件下载。

限制与约定

对于所有数据，保证 $1\le n\le 10^5,1\le k\le 200$。

时间限制：$\texttt{2s}$

空间限制：$\texttt{1GB}$