【模板】子集卷积

这是一道模板题。

给定两个长度为 $2^n$ 的序列 $a_0,a_1,\cdots,a_{2^n-1}$ 和 $b_0,b_1,\cdots,b_{2^n-1}$，你需要求出一个序列 $c_0,c_1,\cdots,c_{2^n-1}$，其中 $c_k$ 满足： $$c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j$$ 其中$~\mid~$表示按位或，$\&$表示按位与。 答案对 $10^9+9$ 取模。

第一行输入一个正整数 $n$ ，表示集合的大小。 第二行有 $2^n$ 个整数，描述了 $a$。 第三行有 $2^n$ 个整数，描述了 $b$。

输出一行 $2^n$ 个整数，表示 $c$。

2
1 0 2 1
2 0 2 1

2 0 6 3

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