Польшар стоит в ряд со многими другими шарами. Точнее, в ряд стоят ровно n шаров. Шары гордятся за свою родную землю — и хотят доказать, что она стронг.
Шары решили начать с выборов ровно m групп шаров, каждая должна состоять либо из одного шара, либо из двух рядом стоящих. Каждый шар может состоять не более чем в одной группе.
Шары хотят впечатлить своих врагов. Они просят вас посчитать количество таких разбиений на группы для каждого m, где 1 ≤ m ≤ k. Выведите отстаток от деления каждого из этих чисел на 998244353, враги все равно будут впечатлены.
Выходные данные
Выведите последовательность из k целых чисел. Число i должно быть равно искомому числу способов выбрать ровно i групп в соответствии с правилами Польшара.
Примечание
В первом примере можно разделить шары на группы следующим образом:
{1}, {2}, {3}, {12}, {23}.
{12}{3}, {1}{23}, {1}{2}, {1}{3}, {2}{3}.
{1}{2}{3}.
Поэтому нужно вывести 5 5 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
|
5 5 1
|
|
2
|
1 1
|
1
|
|
3
|
5 10
|
9 25 25 9 1 0 0 0 0 0
|