У Васи есть массив, состоящий из \(n\) чисел, а также два числа \(k\) и \(len\). Все числа массива либо лежат в отрезке от \(1\) до \(k\) (включительно), либо равны \(-1\). Массив называется хорошим, если в нем нет подотрезка длины \(len\) или более, состоящего из одинаковых чисел.
Сообщите Васе количество способов заменить все \(-1\) на числа от \(1\) до \(k\) (включительно) так, чтобы получившийся массив был хорошим. Так как количество хороших массивов может быть достаточно большим, выведите его по модулю \(998244353\).
Выходные данные
В единственной строке выведите целое число — количество способов заменить все \(-1\) на числа от \(1\) до \(k\) (включительно) так, чтобы получившийся массив был хорошим. Так как ответ может быть очень большим, выведите его по модулю \(998244353\).
Примечание
В перовом тестовом примере существует два способа:
- \([1, 2, 1, 1, 2]\);
- \([1, 2, 1, 2, 2]\).
Во втором тестовом примере не существует ни одного способа сделать массив хорошим, т. к. подотрезок с первого по второй элемент всегда будет состоять из одинаковых чисел.
В третьем тестовом примере перечислить все хорошие массивы не представляется возможным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 3
1 -1 1 -1 2
|
2
|
|
2
|
6 3 2
1 1 -1 -1 -1 -1
|
0
|
|
3
|
10 42 7
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
|
645711643
|