تعلّم الصغير 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$