다차원 합성곱 (순환)

소수 $p$와, $\mathbb{Z}/p\mathbb{Z}$ 위의 $K$변수 다항식 $f(x_1, x_2, ..., x_K)$ 및 $g(x_1, x_2, ..., x_K)$가 주어진다. $\bmod (1-x_1^{N_1}, 1-x_2^{N_2}, ..., 1-x_K^{N_K})$를 적용하여 $f$와 $g$의 곱을 계산한다. 여기서 $N_i$는 $p-1$의 약수이다.

제약 조건

• $2 \leq p \leq 1000000000$
• $p$는 소수이다
• $0 \leq K \leq 18$
• $\prod N_i \leq 262144$
• $2 \leq N_i$
• $N_i$는 $p-1$의 약수이다

$P$ $K$
$N_1$ $N_2$ ... $N_K$
$f$
$g$

$f$, $g$는 $0$ 이상 $p-1$ 이하의 정수로 이루어진 길이 $\prod N_i$의 정수 배열이다. $i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$-번째 원소는 $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$의 계수에 대응한다.

$fg$

$fg$는 $0$ 이상 $p-1$ 이하의 정수로 이루어진 길이 $\prod N_i$의 정수 배열이다. 입력 형식과 마찬가지로, $i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$-번째 원소는 $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$의 계수에 대응한다.