단항식 기저에서 뉴턴 기저로의 변환

다항식 $\displaystyle f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{Z}[x]$와 정수 $p_0, p_1, \ldots, p_{N-1}$가 주어진다.

$\displaystyle f(x) = \sum_{i=0}^{N-1} b_i \prod_{j=0}^{i-1} (x-p_j)$을 만족하는 $b_0, b_1, \ldots, b_{N-1}$를 구하고, 이를 $998244353$로 나눈 나머지를 출력한다.

제약 조건

• $0 \leq N \leq 131072$
• $0 \leq a_i, p_i \lt 998244353$

$N$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
$p_0$ $p_1$ $\cdots$ $p_{N-1}$

$b_0$ $b_1$ $\cdots$ $b_{N-1}$