N הקטן למד לאחרונה על MEX. המונח MEX (Minimum Excluded) מתייחס למספר השלם האי-שלילי הקטן ביותר שאינו מופיע במערך. לדוגמה: $\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$. 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$, N הקטן מגדיר את הפונקציה $f(p)$ כמספר הזוגות של מספרים שלמים $(l, r)$ המקיימים את התנאים הבאים:

• $1 \le l \le r \le n$;
• $p_l, \dots, p_r$ הוא מערך $(r - l + 1)$-טוב.

N הקטן הוכיח את המשפט הבא: עבור כל מערך $n$-טוב $p$, מתקיים $1 \le f(p) \le n$. כעת, N הקטן מקווה שתוכלו למצוא את מספר המערכים ה-$n$-טובים $p$ עבור כל $i \in [1, n]$ כך ש-$f(p) = i$. כמובן, מספר זה עשוי להיות גדול מאוד, ולכן עליכם לספק את התוצאה מודולו $998\,244\,353$.

קלט

הקלט מורכב משורה בודדת המכילה מספר שלם $n$ ($1 \le n \le 10^5$).

פלט

הדפיסו שורה בודדת המכילה $n$ מספרים שלמים, כאשר המספר השלם ה-$i$ מייצג את מספר המערכים ה-$n$-טובים $p$ המקיימים $f(p) = i$, מודולו $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$-טובים, עם ערכי הפונקציה המתאימים:

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