E. Непересекающиеся подперестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы два целых числа $$$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$$$.

Входные данные

Единственная строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 4000$$$).

Выходные данные

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

Примеры
Входные данные
10 3
Выходные данные
71712
Входные данные
2 2
Выходные данные
2
Входные данные
1337 42
Выходные данные
524933698