Slime интересуется последовательностями. Он определил хорошие последовательности положительных целых чисел $p$ длины $n$ следующим образом:

• Для каждого $k>1$, присутствующего в $p$, должна существовать хотя бы одна пара индексов $i, j$ таких, что $1 \leq i < j \leq n$, $p_i = k - 1$ и $p_j = k$.

Для заданного целого числа $n$ обозначим множество всех хороших последовательностей длины $n$ как $s_n$. Для фиксированного целого числа $k$ и последовательности $p$ пусть $f_p(k)$ — количество вхождений числа $k$ в $p$. Для каждого $k$ от $1$ до $n$ Slime хочет узнать следующее значение:

$$\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353$$

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

Первая строка содержит одно целое число $n$ ($1\le n\le 100\,000$).

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

Выведите $n$ целых чисел, где $i$-е из них должно быть равно $\left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353$.

Примеры

Пример 1

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

2

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

3 1

Пример 2

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

3

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

10 7 1

Пример 3

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

1

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

1

Примечание

В первом примере $s=\{[1,1],[1,2]\}$.

Во втором примере $s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}$.

В третьем примере $s=\{[1]\}$.