다항식 보간 (등비수열)

정수 $N, a, r$와 정수 수열 $y_0, y_1, ..., y_{N - 1}$가 주어진다. $0\leq i < j \leq N-1$에 대해 $ar^i\not\equiv ar^j\pmod{998244353}$임이 보장된다.

각 $i$에 대해 $f(ar^i) \equiv y_i \pmod{998244353}$를 만족하는 다항식 $f(x) = \sum_{i = 0}^{N - 1} c_i x^i\in \mathbb{Z}[x]$를 계산한다.

또한, $0 \leq c_i < 998244353$를 만족해야 한다.

제약 조건

• $0 \leq N \leq 524288$
• $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)$

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

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