To prepare for the upcoming school year, Richard has bought ~N~ books for his English class. Each book is assigned a value, ~a_i~, Richard's willingness to read that book.

Richard wants to choose ~k~ of the ~N~ books and calculate his willingness to read those ~k~ books. The willingness to read those ~k~ books is the product of the willingness to read each individual book. For example, if he bought books of value ~a = [2, 5, 7, 9, 13]~, and he chose ~k = 3~ books with indices ~1, 2, 4~, the willingness to read those books would be ~a_1 \cdot a_2 \cdot a_4 = 2 \cdot 5 \cdot 9 = 90~.

Richard wants the sum of the willingness of all distinct combinations of ~k~ books for all values of ~k~ ~(1 \le k \le N)~.

However, since Richard does not like large numbers, he wants each sum modulo ~998\,244\,353~.

Two combinations are considered distinct if the indices of the books chosen are different, regardless of the values of the books.

Input Specification

The first line of input will contain a single integer ~N~ ~(1 \le N \le 2\,000)~, the number of books that Richard bought.

The second line of input will contain ~N~ space-separated integers, the ~i^\text{th}~ integer representing ~a_i~ ~(|a_i| \le 10^9)~, the value of each book.

Output Specification

On one line, print ~N~ space-separated integers, the ~k^\text{th}~ integer representing the sum of the willingness of all distinct combinations of choosing ~k~ books, modulo ~998\,244\,353~.

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)~.

It may or may not help to know that ~998\,244\,353 = 119 \cdot 2^{23} + 1~.

Constraints

Subtask 1 [5%]

~N \le 10~

Subtask 2 [10%]

~N \le 20~

Subtask 3 [35%]

~|a_i| \le 10^3~

Subtask 4 [50%]

No additional constraints.

Sample Input 1

4
1 2 2 3

Sample Output 1

8 23 28 12

Explanation for Sample Output 1

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

There are ~4~ distinct combinations to read ~1~ book:

~a_1 = 1~

~a_2 = 2~

~a_3 = 2~

~a_4 = 3~

Their sum is ~8~.

There are ~6~ distinct combinations to read ~2~ books.

~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 combinations of reading ~3~ books.

~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 distinct combination of reading ~4~ books is ~a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot 2 \cdot 2 \cdot 3 = 12~.

Sample Input 2

3
-1 -1 -1

Sample Output 2

998244350 3 998244352