Задача . E. Непересекающиеся подперестановки

Заданы два целых числа \(n\) и \(k\).

Для массива длины \(n\) давайте определим его стоимость как максимальное количество непрерывных подмассивов этого массива, которые могут быть выбраны следующим образом:

• каждый элемент массива принадлежит не более чем одному подмассиву;
• длина каждого подмассива ровно \(k\);
• каждый подмассив содержит каждое целое число от \(1\) до \(k\) ровно один раз.

Например, если \(n = 10\), \(k = 3\) и массив равен \([1, 2, 1, 3, 2, 3, 2, 3, 1, 3]\), его стоимость равна \(2\), потому что, например, мы можем выбрать два подмассива: от \(2\)-го элемента до \(4\)-го и от \(7\)-го элемента до \(9\)-го, и мы можем показать, что выбрать больше \(2\) подмассивов нельзя.

Посчитайте сумму стоимостей по всем массивам длины \(n\), состоящих из целых чисел от \(1\) до \(k\), и выведите ее по модулю \(998244353\).