时空限制

1S/512M

题目描述

定义一个合法密码由 $n$ 个 $1\sim k$ 之间的数字组成，且其中不能出现连续 $k$ 位相同的情况。

比如当 $n=5$ 且 $k=3$ 时，$32111$ 就不是一个合法密码，因为密码的第 $3\sim 5$ 位都是 $1$；而 $32323$ 是一个合法密码。

已知密码的一部分，求有多少个合法密码满足已知信息，对 $998244353$ 取模。

格式

输入格式

第一行包含两整数 $n,k$，分别表示密码的长度和每位数字的范围。

第二行包含一个长度为 $n$ 的字符串 $S$，其中 $S_i=0$ 表示第 $i$ 位密码未知，否则表示密码的第 $i$ 位为 $S_i$。

输出格式

输出一个整数表示满足已知信息的合法密码的数量，对 $998244353$ 取模。

样例

样例输入 #1

5 3
00303

样例输出 #1

16

样例解释 #1

满足已知信息的合法密码共有 $16$个：$11313$、$11323$、$12313$、$12323$、$13313$、$13323$、$21313$、$21323$、$22313$、$22323$、$23313$、$23323$、$31313$、$31323$、$32313$、$32323$。

样例输入 #2

3 2
102

样例输出 #2

0

样例输入 #3

6 6
100600

样例输出 #3

1296

数据规模

对于 $20\%$ 的数据，$k = 2$。

对于 $60\%$ 的数据，$k \leq 5$。

对于 $100\%$ 的数据，$1\leq n \leq 10^6$，$2\leq k\leq 9$。数据保证 $S$ 仅由 $0\sim k$ 的数字组成。