Note: An equivalent version of this problem is also available on DMOJ here

I have a 1-indexed array named ~a~ with ~N~ elements.

I define a k-product as taking a subset of size ~k~ from the set ~\{1, 2, 3, ..., N\}~ and taking the product of the values of ~a~ at those indexes.

For example, if ~a = [2, 5, 7, 9, 13]~, one valid 3-product is ~a_1 \cdot a_2 \cdot a_4 = 2 \cdot 5 \cdot 9 = 90~.

I define a k-sum of an array as the sum of all distinct k-products that can be formed with it. Two k-products are considered distinct if the subset of indexes are different, regardless of the values at the indexes.

For all ~1 \leq k \leq N~, find the k-sum of ~a~, each modulo ~998244353~.

Input Specification

The first line of input will contain a single integer ~N~.

The second line of input will contain ~N~ space-separated integers, the ~i^{th}~ integer representing ~a_i~.

Output Specification

On one line, print ~N~ space-separated integers, the ~i^{th}~ integer representing the ~i~-sum of ~a~, modulo ~998244353~.

We define ~A~ modulo ~B~ in the 2 equivalent ways:

1. Taking the remainder of ~A \div B~, adding ~B~ if the result is negative.
2. Subtracting ~B~ from ~A~, or adding ~B~ to ~A~, until ~A~ is in the interval ~[0, B)~.

Constraints

~(1 \leq N \leq 2~ ~000)~

~(|a_i| \leq 10^9)~ for all ~(1 \leq i \leq N)~

It may help to know that ~998244353 = 119 \cdot 2^{23} + 1~.

Sample Input

4
1 2 2 3

Sample Output

8 23 28 12

Explanation for Sample Input

~N = 4~, ~a = [1, 2, 2, 3]~.

There are 4 distinct 1-products:

~a_1 = 1~

~a_2 = 2~

~a_3 = 2~

~a_4 = 3~

There are 6 distinct 2-products.

~a_1 \cdot a_2 = 1 \cdot 2 = 2~

~a_1 \cdot a_3 = 1 \cdot 2 = 2~

~a_1 \cdot a_4 = 1 \cdot 3 = 3~

~a_2 \cdot a_3 = 2 \cdot 2 = 4~

~a_2 \cdot a_4 = 2 \cdot 3 = 6~

~a_3 \cdot a_4 = 2 \cdot 3 = 6~

Their sum is ~23~.

There are 4 distinct 3-products.

~a_1 \cdot a_2 \cdot a_3 = 1 \cdot 2 \cdot 2 = 4~

~a_1 \cdot a_2 \cdot a_4 = 1 \cdot 2 \cdot 3 = 6~

~a_1 \cdot a_3 \cdot a_4 = 1 \cdot 2 \cdot 3 = 6~

~a_2 \cdot a_3 \cdot a_4 = 2 \cdot 2 \cdot 3 = 12~

Their sum is ~28~.

The only 4-product is ~1 \cdot 2 \cdot 2 \cdot 3 = 12~.