F. Вася и массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть массив, состоящий из $$$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
Примечание

В перовом тестовом примере существует два способа:

  1. $$$[1, 2, 1, 1, 2]$$$;
  2. $$$[1, 2, 1, 2, 2]$$$.

Во втором тестовом примере не существует ни одного способа сделать массив хорошим, т. к. подотрезок с первого по второй элемент всегда будет состоять из одинаковых чисел.

В третьем тестовом примере перечислить все хорошие массивы не представляется возможным.