#152. 子集卷积

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB | 显示标签 通过: 572 | 提交: 1027

题目描述

这是一道模板题。

给出两个集合幂级数 $f, g$ ，求它们的不相交集合并卷积。

卷积在模 $10^9 + 9$ 意义下进行。

第一行输入一个数 $n$ ，表示集合的大小。

第二行有 $2^n$ 个数，描述了 $f$ 。

第三行有 $2^n$ 个数，描述了 $g$ 。

输出一行 $2^n$ 个数，表示 $f$ 和 $g$ 卷积后的结果。

输入

2
1 0 2 1
2 0 2 1

输出

2 0 6 3

对于所有数据， $1 \le n \le 20, 0 \le f_i, g_i < 10^9 + 9$ 。