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]\}$.