Dostępnych jest kilka rodzajów klejnotów, przy czym istnieje $a_k$ rodzajów klejnotów o wadze $k$. Chcesz dowiedzieć się, dla każdego $w \le n$, ile istnieje sposobów ułożenia naszyjnika z klejnotów tak, aby naszyjnik zawierał co najmniej $2$ klejnoty, każde dwa sąsiednie klejnoty należały do różnych rodzajów, a całkowita waga naszyjnika wynosiła $w$. Wynik należy podać modulo $998244353$.
Uwaga:
- Pierwszy i ostatni klejnot w naszyjniku również muszą być różnych rodzajów.
- Jeśli dwa układy można przekształcić jeden w drugi poprzez obrót lub odbicie, należy je uznać za różne sposoby.
Wejście
W pierwszej linii znajduje się liczba całkowita dodatnia $n$.
W drugiej linii znajduje się $n$ liczb, gdzie $k$-ta liczba oznacza $a_k$.
Wyjście
Wypisz w jednej linii $n + 1$ liczb, odpowiadających liczbie sposobów dla $w=0, 1, \dots, n$.
Przykład
Przykład 1
Wejście
5 2 1 0 1 0
Wyjście
0 0 2 4 8 12
Uwagi
Poniższe zapisy można uznać za generowane przez obroty:
$$ 2:[1,1']\times 2\\ 3:[1,2]\times 2,[1',2] \times 2\\ 4:[1,1',1,1'] \times 2,[1,1',2]\times 3,[1',1,2]\times 3\\ 5:[1,4]\times 2, [1',4]\times 2, [1,1',1,2]\times 4, [1',1,1',2]\times 4 $$
Przykład 2
Patrz załączone pliki.
Ograniczenia
Dla $100\%$ danych wejściowych: $2 \le n \le 10^5, 0 \le a_i < 998244353$.
| Numer testu | $n$ | Ograniczenia specjalne |
|---|---|---|
| $1$ | $\le 8$ | |
| $2$ | $\le 50$ | |
| $3$ | $\le 10^5$ | istnieją tylko klejnoty o wadze $1$ |
| $4$ | $\le 3\times 10^2$ | |
| $5$ | ||
| $6$ | ||
| $7$ | $\le 3\times 10^3$ | |
| $8$ | ||
| $9$ | $\le 10^5$ | |
| $10$ |