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

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})$.

3 3 3
3 3 3

9 39 273

Hint

For $100\%$ of the testdata, $1 \le n, m \le 10^6$, $0 \le c, a_i < 998244353$.

Translated by ChatGPT 5