P6097 [Template] Subset Convolution

This is a template problem.

Given two sequences of length $2^n$, $a_0,a_1,\cdots,a_{2^n-1}$ and $b_0,b_1,\cdots,b_{2^n-1}$, you need to compute a sequence $c_0,c_1,\cdots,c_{2^n-1}$, where $c_k$ satisfies: $$c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j$$ Here, $~\mid~$ denotes bitwise OR, and $\&$ denotes bitwise AND. The answer should be taken modulo $10^9+9$.

The first line contains a positive integer $n$, representing the size of the set. The second line contains $2^n$ integers, describing $a$. The third line contains $2^n$ integers, describing $b$.

Output one line with $2^n$ integers, representing $c$.

For all testdata, $1\le n\le 20$, $0\le a_i,b_i< 10^9+9$. Translated by ChatGPT 5