Городок 1

Алексей со своими друзьями играет в интересную игру. На асфальте мелом рисуют правильный K-угольник. Около каждой вершины подписывают её номер начиная с 1. Каждый из участников игры стоит в вершине этого многоугольника, таким образом присваивая себе номер вершины. Номер у участника в процессе игры не меняется. В центре многоугольника стоит ведущий и озвучивает произвольное число N. Каждый из участников перемещается по вершинам правильного K-угольника, переходя каждый раз в одну из соседних вершин. После того, как всеми участниками было сделано N переходов, каждый участник останавливается в какой-то вершине. Переход - это перемещение от одной вершины до соседней по ребру многоугольника. После этого подсчитывается балл каждого участника.

Балл - это абсолютная разность между начальным номером участника и номером вершины в конце игры. Выигрывает тот, у кого будет наименьший балл. Алексей сразу понял, что лучший вариант вернуться в начальную вершину, тогда балл будет равен 0.

Сколькими способами Алексей может попасть из начальной вершины обратно в эту же вершину за N переходов? Число способов может быть велико, поэтому выведите ответ по модулю 998244353.

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

Входной файл INPUT.TXT содержит два натуральных числа K, N (3 ≤ K ≤ 1000; 1 ≤ N ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу по модулю 998244353.

Примеры

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]