卷积（Convolution (Mod 1,000,000,007)）

问题描述

给定两个整数序列 $a_0, a_1, \dots, a_{N-1}$ 和 $b_0, b_1, \dots, b_{M-1}$，计算它们的离散卷积序列 $c_0, c_1, \dots, c_{(N-1)+(M-1)}$，其中：

$$c_k = \sum_{\substack{i+j = k \\ 0 \le i < N \\ 0 \le j < M}} a_i b_j \bmod 1000000007.$$

约束条件

• $1 \leq N, M \leq 2^{19}$
• $0 \leq a_i, b_i < 1000000007$

输入格式

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

输出格式

$c_0\ c_1\ \cdots\ c_{N+M-2}$

4 5
1 2 3 4
5 6 7 8 9

5 16 34 60 70 70 59 36

1 1
10000000
10000000

999300007