Evaluating a Polynomial at Exponential Points

Given a polynomial \(P(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}\) with \(n\) terms, an integer base \(c\) and an integer \(m\), you are required to compute the values:

\(P(c^0), P(c^1), \dots, P(c^{m-1})\)

All results should be computed modulo \(998244353\).

inputFormat

The first line contains three space-separated integers: \(n\), \(c\), and \(m\) where:

• \(n\) is the number of coefficients of the polynomial \(P(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}\).
• \(c\) is the base used for exponentiation.
• \(m\) is the number of points at which the polynomial is evaluated.

The second line contains \(n\) space-separated integers \(a_0, a_1, \dots, a_{n-1}\) representing the coefficients of \(P(x)\).

outputFormat

Output \(m\) space-separated integers where the \(k\)-th integer is \(P(c^k) \bmod 998244353\) for \(k = 0, 1, \dots, m-1\).

sample

3 2 4
1 2 3

6 17 57 209