3928: 子集卷积
内存限制：512 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这是一道模板题。
给出两个集合幂级数 $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 \leq n \leq 20, 0 \leq f_i, g_i < 10^9 + 9$。