Pikku N on äskettäin oppinut MEX-käsitteen. MEX (Minimum Excluded) tarkoittaa pienintä epänegatiivista kokonaislukua, joka ei esiinny taulukossa. Esimerkiksi: $\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$. Pikku N määrittelee, että pituuden $k$ epänegatiivisten kokonaislukujen taulukolle $[b_1, b_2, \dots, b_k]$, jos $\operatorname{MEX}([b_1, b_2, \dots, b_k]) = k$, niin taulukkoa $b$ kutsutaan $k$-hyväksi taulukoksi.

Annettuna positiivinen kokonaisluku $n$, $n$-hyvälle taulukolle $p_1, p_2, \dots, p_n$ Pikku N määrittelee funktion $f(p)$ niiden kokonaislukuparien $(l, r)$ lukumääräksi, jotka täyttävät seuraavat ehdot:

• $1 \le l \le r \le n$;
• $p_l, \dots, p_r$ on $(r - l + 1)$-hyvä taulukko.

Pikku N on todistanut seuraavan lauseen: mille tahansa $n$-hyvälle taulukolle $p$ pätee $1 \le f(p) \le n$. Nyt Pikku N toivoo sinun selvittävän jokaiselle $i \in [1, n]$ niiden $n$-hyvien taulukoiden $p$ lukumäärän, joille $f(p) = i$. Tämä lukumäärä voi tietysti olla hyvin suuri, joten tulos tulee ilmoittaa modulo $998\,244\,353$.

Syöte

Syöte koostuu yhdestä rivistä, joka sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$).

Tuloste

Tulosta yksi rivi, joka sisältää $n$ kokonaislukua, missä $i$:s kokonaisluku ilmaiseva ehtoa $f(p) = i$ vastaavien $n$-hyvien taulukoiden $p$ lukumäärän modulo $998\,244\,353$.

Esimerkit

Esimerkkisyöte 1

1

Esimerkkituloste 1

1

Esimerkkisyöte 2

3

Esimerkkituloste 2

0 2 4

Esimerkkisyöte 3

7

Esimerkkituloste 3

0 2312 1424 728 352 160 64

Huomautus

Kun $n = 3$, voidaan todistaa, että on olemassa kuusi $3$-hyvää taulukkoa, joiden vastaavat funktion arvot ovat:

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