다항식의 합성

$\mathbb{Z}/2\mathbb{Z}$ 위의 다항식 $f(x)$, $g(x)$, $h(x)$가 주어진다. 다항식 $f(g(x)) \bmod h(x)$를 구하시오.

첫 세 줄에 다항식 $f$, $g$, $h$가 한 줄에 하나씩 주어진다. 각 다항식 $p$는 $n$ $p_0$ $p_1$ $p_2$ $\dots$ $p_n$ 형태로 주어진다 ($1 \le n \le 4000$, 모든 $i$에 대해 $p_i \in \{0, 1\}$, $p_n = 1$). 이때 다항식 $p(x)$는 $p_0 + p_1 x + p_2 x^2 + \dots + p_n x^n$이다.

결과 다항식을 입력과 같은 형식으로 출력한다. 결과가 영다항식이면 0 0을 출력한다.

$\mathbb{Z}/2\mathbb{Z}$는 원소가 $0$과 $1$인 두 개의 값으로 이루어진 집합이다. 덧셈, 뺄셈, 곱셈, 나눗셈의 결과는 대응하는 정수 연산 결과를 $2$로 나눈 나머지이다.

이 체 위의 다항식은 $f_n x^n + f_{n-1} x^{n-1} + \ldots + f_1 x + f_0$ 꼴이며, 각 계수는 $0$ 또는 $1$이다. $x$도 $\mathbb{Z}/2\mathbb{Z}$의 값을 가질 수 있다. 다항식의 차수는 $f_n \ne 0$을 만족하는 가장 큰 $n$이다.

두 다항식은 모든 계수가 같을 때 같다. 덧셈과 뺄셈은 계수별로 계산한다. $a(x) \pm b(x) = \sum_k (a_k \pm b_k) x^k$이다. $a(x)$와 $b(x)$의 곱 $c(x) = \sum_k c_k x^k$에서 $c_s = \sum_{t=0}^{s} a_t b_{s-t}$이다.

0이 아닌 다항식 $b(x)$에 대해 $q(x) b(x) + r(x) = a(x)$이고 $r(x)$의 차수가 $b(x)$의 차수보다 작으면, $a(x) / b(x) = q(x)$, $a(x) \bmod b(x) = r(x)$라고 쓴다. $q(x)$와 $r(x)$는 하나로 정해진다.

합성 $a(b(x))$는 $\sum_k a_k (b(x))^k$이다. 여기서 $(b(x))^0 = 1$, $(b(x))^1 = b(x)$, $p > 1$일 때 $(b(x))^p = b(x) \cdot (b(x))^{p-1}$이다. 식을 전개한 뒤 같은 차수의 계수를 더한다.