Little N は最近 MEX について学びました。MEX（Minimum Excluded）とは、配列内に現れない最小の非負整数のことです。例えば、$\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$ です。Little N は、長さ $k$ の非負整数配列 $[b_1, b_2, \dots, b_k]$ に対して $\operatorname{MEX}([b_1, b_2, \dots, b_k]) = k$ が成り立つとき、配列 $b$ を $k$-良配列と呼ぶことにしました。

正の整数 $n$ が与えられます。$n$-良配列 $p_1, p_2, \dots, p_n$ に対して、Little N は以下の条件を満たす整数の組 $(l, r)$ の個数を関数 $f(p)$ として定義します：

• $1 \le l \le r \le n$；
• $p_l, \dots, p_r$ は $(r - l + 1)$-良配列である。

Little N は次の定理を証明しました：任意の $n$-良配列 $p$ に対して $1 \le f(p) \le n$ が成り立つ。いま Little N は、各 $i \in [1, n]$ について $f(p) = i$ を満たす $n$-良配列 $p$ の個数を求めてほしいと考えています。この個数は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

入力は $1$ 行からなり、整数 $n$ ($1 \le n \le 10^5$) が与えられます。

出力

$1$ 行に $n$ 個の整数を出力してください。$i$ 番目の整数は、$f(p) = i$ を満たす $n$-良配列 $p$ の個数を $998\,244\,353$ で割った余りを表します。

入出力例

入力例 1

1

出力例 1

1

入力例 2

3

出力例 2

0 2 4

入力例 3

7

出力例 3

0 2312 1424 728 352 160 64

注記

$n = 3$ のとき、$3$-良配列は $6$ 個存在し、対応する関数の値は次のようになります：

$f([0, 1, 2]) = 3$, $f([0, 2, 1]) = 2$, $f([1, 0, 2]) = 3$, $f([1, 2, 0]) = 2$, $f([2, 0, 1]) = 3$, $f([2, 1, 0]) = 3$