Description

Given an $n$-term polynomial $P(x)$ and $c, m$, compute $P(c^0), P(c^1), \dots, P(c^{m-1})$. All answers are taken modulo $10^9+7$.

Input Format

The first line contains three positive integers $n, c, m$.
The second line contains $n$ non-negative integers $a_0, a_1, \dots, a_{n-1}$, representing the coefficients of $P(x)$ from low degree to high degree.

Output Format

Output one line with $m$ positive integers. The $i$-th number represents $P(c^{i-1})$.

6 108616 6
1 0 8 6 1 6

22 772456230 866731294 299746576 978045696 394365866

Hint

For $100\%$ of the testdata, $1 \le n, m \le 6\cdot10^5$, $0 \le c, a_i < 10^9+7$.
| Test Point ID | Limits on $n, m$ | | :-----------: | :-----------: | | $1$ | $n=m=1000$ | | $2$ | $n=m=64000$ | | $3$ | $n=m=5\cdot10^5$ | | $4$ | $n=5\cdot10^5,m=6\cdot10^5$ | | $5$ | $n=6\cdot10^5,m=5\cdot10^5$ |

The problem setter regrets that, due to precision and the limitations of Luogu’s built-in materials, it cannot be extended to $10^6$.
Hint: $7$ FFT runs might not pass.
Hint: The problem setter did not use long double.

Translated by ChatGPT 5