Гости по юртам
На джайлоо Сон-Куль приехали n туристов, и для них поставили юрты. Все юрты одинаковые, а туристы различаются. Хозяйка Жылдыз хочет знать, сколькими способами можно расселить туристов ровно в k юрт так, чтобы ни одна юрта не пустовала. Два способа различаются, если в одном из них два туриста живут в одной юрте, а в другом — в разных (юрты между собой не различаются).
Хозяйка ещё не знает, сколько юрт поставят, поэтому просит ответ сразу для всех k = 1, 2, …, K. Ответы выведите по модулю 998244353.
Входные данные
В единственной строке — два целых числа n и K (1 ≤ n ≤ 10¹⁸, 1 ≤ K ≤ 2 · 10⁵).
Выходные данные
Выведите K чисел через пробел: количество способов для k = 1, …, K по модулю 998244353.
Пример 1
Вход:
4 5
Выход:
1 7 6 1 0
Пояснение
Четырёх туристов в одну юрту можно поселить одним способом, в две — семью (3 + 1 четырьмя способами и 2 + 2 тремя), в три — шестью (выбираем пару, которая живёт вместе), в четыре — одним. В пять юрт четырёх туристов не расселить.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, K ≤ 40, ещё в 5 % тестов n, K ≤ 1000.
Подсказка
Это числа Стирлинга второго рода. По формуле включений-исключений k! · S(n, k) = Σ_{j=0}^{k} (−1)^(k−j) C(k, j) j^n, а это свёртка двух последовательностей.
Комментарии