Vasya 得到了一个由 $$$n$$$ 整数组成的数组,另外还有两个整数 $$$k$$$ 和 $$$len$$$ 。数组中的所有数字要么介于 $$$1$$$ 和 $$$k$$$(含)之间,要么等于 $$$-1$$$。如果没有 $$$len$$$ 连续相等数字的段,则该数组是好的。
Vasya 会将每个 $$$-1$$$ 替换为 $$$1$$$ 到 $$$k$$$(含)之间的某个数字,这样生成的数组就很好。告诉他进行这种替换的方法有多少种。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。
输入
第一行包含三个整数 $$$n、k$$$ 和 $$$len$$$ ($$$1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n$$$)。
第二行包含 $$$n$$$ 数字 — 数组。每个数字要么为$$$-1$$$,要么在$$$1$$$ 和$$$k$$$ 之间(含)。
输出
打印一个整数 — 将每个 $$$-1$$$ 替换为 $$$1$$$ 到 $$$k$$$(含)之间的某个数字的方法数,因此该数组是好的。答案可能很大,所以打印它对 $$$998244353$$$ 取模。
示例
输入 #1
5 2 3 1 -1 1 -1 2
输出 #1
2
输入 #2
6 3 2 1 1 -1 -1 -1 -1
输出 #2
0
输入 #3
10 42 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
输出 #3
645711643
注意
第一次测试中可能的答案:
1. $$$[1, 2, 1, 1, 2]$$$;
2. $$$[1, 2, 1, 2, 2]$$$.
无法在第二次测试中使数组变得良好,因为前两个元素相等。
第三次测试的答案太多了,所以我们不会描述任何答案。