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

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 2000)$, 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 $998244353$.

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

1. Taking the remainder of $A÷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 $998244353=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