读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：password.in

输出：password.out

题目描述

定义一个长度为 $n$ 的密码序列，每一位都是 $1\sim k$ 之间的数字。

如果某个数字连续出现了恰好 $k$ 位（即出现长度为 $k$ 的连续相同子段），则该密码非法；否则为合法密码。

例如当 $n=5,k=3$ 时，32111 不是合法密码（第 3 到第 5 位均为 1），而 32323 是合法密码。

现在给出一个长度为 $n$ 的模板串 $s$，其中每个字符都在 0 到 9 之间，含义如下：

• 若 $s_i=0$，表示第 $i$ 位未知，可以填写任意 $1\sim k$ 的数字；
• 若 $1\le s_i\le k$，表示第 $i$ 位已经固定为该数字。

请你计算：满足模板信息且为合法密码的方案数。答案对 $998244353$ 取模。

输入格式

输入共两行。

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

第二行一个长度为 $n$ 的字符串 $s$。

保证 $1 \le n \le 10^6$，$2 \le k \le 9$，且对任意位置 $i$，$s_i=0$ 或 $1 \le s_i \le k$。

输出格式

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

输入输出样例

5 3
32000

22

说明/提示

样例中前两位固定为 3 和 2，后三位可自由填写，但不能出现长度为 3 的连续相同数字。