У Васи есть массив, состоящий из \(n\) чисел, а также два числа \(k\) и \(len\). Все числа массива либо лежат в отрезке от \(1\) до \(k\) (включительно), либо равны \(-1\). Массив называется хорошим, если в нем нет подотрезка длины \(len\) или более, состоящего из одинаковых чисел.
Сообщите Васе количество способов заменить все \(-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\).
В перовом тестовом примере существует два способа:
Во втором тестовом примере не существует ни одного способа сделать массив хорошим, т. к. подотрезок с первого по второй элемент всегда будет состоять из одинаковых чисел.
В третьем тестовом примере перечислить все хорошие массивы не представляется возможным.
5 2 3 1 -1 1 -1 2
2
6 3 2 1 1 -1 -1 -1 -1
0
10 42 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
645711643
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач