#81. 子集卷积

子集卷积

当前没有测试数据。

题目描述

这是一道模板题。

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

卷积在模 109+910^9 + 9 意义下进行。

输入格式

第一行输入一个数 nn,表示集合的大小。

第二行有 2n2^n 个数,描述了 ff

第三行有 2n2^n 个数,描述了 gg

输出格式

输出一行 2n2^n 个数,表示 ffgg 卷积后的结果。

样例

2
1 0 2 1
2 0 2 1
2 0 6 3

数据范围与提示

对于所有数据,1n20,0fi,gi<109+91 \leq n \leq 20, 0 \leq f_i, g_i < 10^9 + 9