Little N gần đây đã học về MEX. MEX (Minimum Excluded) chỉ số nguyên không âm nhỏ nhất không xuất hiện trong mảng. Ví dụ: $\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$. Little N định nghĩa rằng với một mảng số nguyên không âm độ dài $k$, $[b_1, b_2, \dots, b_k]$, nếu $\operatorname{MEX}([b_1, b_2, \dots, b_k]) = k$ thì mảng $b$ được gọi là mảng $k$-tốt.

Cho số nguyên dương $n$, với một mảng $n$-tốt $p_1, p_2, \dots, p_n$, Little N định nghĩa hàm $f(p)$ là số cặp số nguyên $(l, r)$ thỏa mãn các điều kiện sau:

• $1 \le l \le r \le n$;
• $p_l, \dots, p_r$ là một mảng $(r - l + 1)$-tốt.

Little N đã chứng minh được định lý sau: với mọi mảng $n$-tốt $p$, luôn có $1 \le f(p) \le n$. Bây giờ, Little N hy vọng bạn có thể tìm số lượng mảng $n$-tốt $p$ sao cho $f(p) = i$ ứng với mỗi $i \in [1, n]$. Tất nhiên, con số này có thể rất lớn, vì vậy bạn cần đưa ra kết quả chia lấy dư cho $998\,244\,353$.

Dữ liệu vào

Dữ liệu vào gồm một dòng duy nhất chứa số nguyên $n$ ($1 \le n \le 10^5$).

Kết quả

In ra một dòng duy nhất chứa $n$ số nguyên, trong đó số nguyên thứ $i$ biểu thị số lượng mảng $n$-tốt $p$ thỏa mãn $f(p) = i$, chia lấy dư cho $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

1

Kết quả 1

1

Dữ liệu vào 2

3

Kết quả 2

0 2 4

Dữ liệu vào 3

7

Kết quả 3

0 2312 1424 728 352 160 64

Giải thích

Với $n = 3$, có thể chứng minh rằng có sáu mảng $3$-tốt, với các giá trị hàm tương ứng là:

$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$