다항식의 역원

이 문제에서는 $\mathbb{F}_{998244353}$ 위의 다항식을 다룬다.

다항식 $f(x)=\sum_{i=0}^{N-1} a_ix^i$와 $g(x)=\sum_{i=0}^{M-1}b_ix^i$가 주어진다. 다음 조건을 만족하는 다항식 $h(x)=\sum_{i=0}^{T-1}c_ix^i$를 계산한다.

• $\deg(h) < \deg(g)$이고
• $f(x)h(x)\equiv1\pmod {g(x)}$

이 성립한다.

이 문제에서는 $\deg(0)=-\infty$임에 유의한다. $h(x)$가 존재한다면 유일함을 증명할 수 있다. 존재하지 않으면 $-1$를 출력한다.

제한 조건

• $1 \leq N \leq 50000$
• $1 \leq M \leq 50000$
• $0 \leq a_i < 998244353$
• $0 \leq b_i < 998244353$
• $a_{N-1} \neq 0$
• $b_{M-1} \neq 0$

$N$ $M$
$a_0$ $a_1$ $\ldots$ $a_{N - 1}$
$b_0$ $b_1$ $\ldots$ $b_{M - 1}$

$h(x)$가 존재하지 않으면 $-1$를 출력한다.

$h(x)$가 존재하면 첫째 줄에 $T$ ($c_{T-1} \neq 0$)를 출력하고, $h(x)=0$인 경우에는 $T = 0$를 출력한다. 다음 줄에 $c_0, c_1, \ldots, c_{T-1}$를 출력한다.

$T$
$c_0$ $c_1$ $\ldots$ $c_{T - 1}$