Litli N lærði nýlega um MEX. MEX (Minimum Excluded) vísar til minnstu óneikvæðu heiltölunnar sem kemur ekki fyrir í fylki. Til dæmis: $\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$. Litli N skilgreinir að fyrir fylki óneikvæðra heiltalna af lengd $k$, $[b_1, b_2, \dots, b_k]$, ef $\operatorname{MEX}([b_1, b_2, \dots, b_k]) = k$, þá kallast fylkið $b$ $k$-gott fylki.

Gefin er jákvæð heiltala $n$. Fyrir $n$-gott fylki $p_1, p_2, \dots, p_n$ skilgreinir Litli N fallið $f(p)$ sem fjölda heiltalnapara $(l, r)$ sem uppfylla eftirfarandi skilyrði:

• $1 \le l \le r \le n$;
• $p_l, \dots, p_r$ er $(r - l + 1)$-gott fylki.

Litli N hefur sannað eftirfarandi setningu: fyrir sérhvert $n$-gott fylki $p$ gildir $1 \le f(p) \le n$. Nú vonar Litli N að þú getir fundið fjölda $n$-góðra fylkja $p$ fyrir hvert $i \in [1, n]$ þannig að $f(p) = i$. Auðvitað getur þessi tala verið mjög stór, svo þú þarft að gefa niðurstöðuna módúló $998\,244\,353$.

Inntak

Inntakið samanstendur af einni línu sem inniheldur heiltölu $n$ ($1 \le n \le 10^5$).

Úttak

Prentið eina línu sem inniheldur $n$ heiltölur, þar sem $i$-ta heiltalan táknar fjölda $n$-góðra fylkja $p$ sem uppfylla $f(p) = i$, módúló $998\,244\,353$.

Dæmi

Sýnidæmi 1 — Inntak

1

Sýnidæmi 1 — Úttak

1

Sýnidæmi 2 — Inntak

3

Sýnidæmi 2 — Úttak

0 2 4

Sýnidæmi 3 — Inntak

7

Sýnidæmi 3 — Úttak

0 2312 1424 728 352 160 64

Athugasemd

Fyrir $n = 3$ má sanna að til séu sex $3$-góð fylki, með samsvarandi fallgildi:

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