JOHNKRAM ostatnio zajmuje się teorią grafów. Dzisiaj napotkał następujące zadanie: dany jest graf skierowany bez wielokrotnych krawędzi i pętli własnych. Należy obliczyć, ile wierzchołków o stopniu wejściowym $0$ posiada graf po skondensowaniu jego silnie spójnych składowych do pojedynczych wierzchołków.

JOHNKRAM z łatwością rozwiązał to zadanie za pomocą algorytmu Tarjana. Zauważył jednak, że wiele osób napisało znacznie krótszy kod, więc poprosił o ich programy i odkrył, że zawsze wypisują one $1$ = =. Czyżby losowe dane były aż tak słabe? Wygenerował więc wiele losowych grafów skierowanych i odkrył, że odpowiedź rzeczywiście zawsze wynosi $1$ = =. Zmienił zatem sposób generowania losowego, tworząc grafy, w których rozmiar każdej silnie spójnej składowej należy do pewnego zbioru $S$, i wtedy odpowiedź natychmiast wzrosła.

Teraz JOHNKRAM wyeliminował te rozwiązania, ale chce udowodnić siłę swoich danych, więc postawił następujące pytanie: jaka jest wartość oczekiwana odpowiedzi na poprzednie pytanie dla wszystkich etykietowanych grafów skierowanych o $i$ wierzchołkach ($1\leq i\leq n$), w których rozmiar każdej silnie spójnej składowej należy do zbioru $S$? Nie potrafiąc tego udowodnić, zwraca się do Ciebie o pomoc.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą dodatnią $n$, oznaczającą maksymalną liczbę wierzchołków w generowanych grafach skierowanych.

Następnie $n$ linii, z których $i$-ta zawiera liczbę całkowitą $s_i$. Jeśli $s_i=1$, to $i$ należy do zbioru $S$, w przeciwnym razie $i$ nie należy do zbioru $S$.

Wyjście

Wypisz $n$ linii, z których każda zawiera jedną liczbę całkowitą. Liczba w $i$-tej linii oznacza wartość oczekiwaną odpowiedzi na poprzednie pytanie dla wszystkich etykietowanych grafów skierowanych o $i$ wierzchołkach ($1\leq i\leq n$), w których rozmiar każdej silnie spójnej składowej należy do zbioru $S$, modulo $998244353$. Jeśli nie istnieją żadne poprawne grafy skierowane, wypisz $0$. Jeśli wartość oczekiwana wynosi $a/b$ (gdzie $a$ i $b$ są względnie pierwszymi liczbami całkowitymi dodatnimi), wypisana liczba $x$ musi spełniać warunek $bx\equiv a \pmod{998244353}$ oraz $0\leq x < 998244353$.

Przykład

Przykład 1

3
1
0
0

Wyjście 1

1
332748119
519087065

Uwagi

Dla grafów skierowanych o $1$ wierzchołku istnieje $1$ poprawny graf, w którym odpowiedź wynosi $1$, więc wartość oczekiwana to $1$, co po modulo $998244353$ daje $1$.

Dla grafów skierowanych o $2$ wierzchołkach istnieją $2$ poprawne grafy z odpowiedzią $1$ oraz $1$ poprawny graf z odpowiedzią $2$, więc wartość oczekiwana wynosi $\frac{4}{3}$, co po modulo $998244353$ daje $332748119$.

Dla grafów skierowanych o $3$ wierzchołkach istnieje $15$ poprawnych grafów z odpowiedzią $1$, $9$ poprawnych grafów z odpowiedzią $2$ oraz $1$ poprawny graf z odpowiedzią $3$, więc wartość oczekiwana wynosi $\frac{36}{25}$, co po modulo $998244353$ daje $519087065$.

Ograniczenia

Dla wszystkich danych testowych $1\leq n\leq 100000$, $0\leq s_i\leq 1$.