Given a polynomial $A(z)=\sum^{n-1}_{i=0} a_iz^i$, compute $\exp A(z) \bmod {z^n} = \sum^{n-1}_{i=0} c_iz^i$.
Input
The first line of input contains an integer $n$.
The next line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$. It is guaranteed that $a_0=0$.
Output
Output a single line containing $n$ integers, representing $c_0, c_1, \dots, c_{n-1}$, modulo 998244353.
Examples
Input 1
6
0 1 2 3 4 5Output 1
1 1 499122179 166374064 291154613 690452363Subtasks
For all data, $1 \leq n \leq 10^6$, $0 \le a_i < 998\,244\,353$, and $a_0 = 0$.
| Subtask | $n \le$ | Score |
|---|---|---|
| 1 | 100 | 10 |
| 2 | $5 \cdot 10^3$ | 10 |
| 3 | $3 \cdot 10^4$ | 10 |
| 4 | $10^5$ | 10 |
| 5 | $1.5 \cdot 10^5$ | 10 |
| 6 | $2 \cdot 10^5$ | 10 |
| 7 | $3 \cdot 10^5$ | 10 |
| 8 | $5 \cdot 10^5$ | 10 |
| 9 | $7 \cdot 10^5$ | 10 |
| 10 | $10^6$ | 10 |