There are several types of gemstones, where there are $a_k$ types of gemstones with weight $k$. You want to find, for each $w \le n$, the number of necklaces made of these gemstones such that the necklace contains at least $2$ gemstones, every pair of adjacent gemstones belongs to different types, and the total weight of the necklace is $w$. The answer should be taken modulo $998244353$.

Note:

• The first gemstone and the last gemstone of the necklace must also belong to different types.
• If two configurations can be transformed into each other by rotation or reflection, they are still considered different configurations.

Input

The first line contains a positive integer $n$.

The next line contains $n$ integers, where the $k$-th number represents $a_k$.

Output

Output $n + 1$ integers, representing the number of configurations for $w=0, 1, \dots, n$ respectively.

Examples

Input 1

5
2 1 0 1 0

Output 1

0 0 2 4 8 12

Note 1

The following multiplication signs can be considered as rotation generation:

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

Input 2

See the provided files.

Output 2

See the provided files.

Constraints

For $100\%$ of the data, it is guaranteed that $2 \le n \le 10^5$ and $0 \le a_i < 998244353$.