Given a polynomial $A(z)=\sum^{n-1}_{i=0} a_ix^i$, find $A^{-1}(z) \bmod {x^n} = \sum^{n-1}_{i=0} c_iz^n$.
Input
The first line of input contains an integer $n$.
The next line contains $n$ integers $a_0,a_1,\cdots,a_{n-1}$.
Output
Output a single line containing $n$ integers, representing $c_0,c_1,\cdots,c_{n-1}$.
Examples
Input 1
8
1 9 2 6 0 8 1 7Output 1
1 998244344 79 998243654 6187 998189586 484794 993952989Subtasks
For all data, $1 \leq n \leq 10^6$, $0 \le a_i < 998\,244\,353$, $a_0 \ne 0$.
| Test Case | $n$ |
|---|---|
| $1$ | $100$ |
| $2$ | $5 \times 10^3$ |
| $3$ | $3 \times 10^4$ |
| $4$ | $10^5$ |
| $5$ | $10^6$ |