Problem11318--[yosupo] Polynomial - Polynomial Interpolation (Geometric Sequence)

11318: [yosupo] Polynomial - Polynomial Interpolation (Geometric Sequence)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

Given integers $N, a, r$ and integer sequence $y_0, y_1, ..., y_{N - 1}$.
It is guaranteed that $ar^i\not\equiv ar^j\pmod{998244353}$ for $0\leq i < j \leq N-1$. 

Calculate a polynomial $f(x) = \sum_{i = 0}^{N - 1} c_i x^i\in \mathbb{Z}[x]$ s.t. $f(ar^i) \equiv y_i \pmod{998244353}$ is satisfied for each $i$.

Also, $0 \leq c_i < 998244353$ must be satisfied.

Input

$N$ $a$ $r$
$y_0$ $y_1$ ... $y_{N-1}$

Output

$c_0$ $c_1$ ... $c_{N -1}$

Constraints

- $0 \leq N \leq 2^{19}$
- $0 \leq a < 998244353$
- $0 \leq r < 998244353$
- $0 \leq y_i < 998244353$
- $ar^i\not\equiv ar^j \pmod{998244353}$ $(0\leq i < j \leq N-1)$

Sample 1 Input

4 2 10
17 1241 120401 12004001

Sample 1 Output

1 2 3 0

Sample 2 Input

1 0 0
100

Sample 2 Output

100

HINT

Yosupo.

Source/Category