← 返回题目列表

Codeforces · 1093/F

F. Vasya 和阵列

中文机器翻译题面 查看原题

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]$$$.

无法在第二次测试中使数组变得良好,因为前两个元素相等。

第三次测试的答案太多了,所以我们不会描述任何答案。