# Subset Convolution

AC一覧

## Problem Statement問題文

Given size $2^N$ integer sequences $a_0, a_1, \dots, a_{2^N - 1}$ and $b_0, b_1, \dots, b_{2^N - 1}$. Calculate an integer sequence $c_0, c_1, \dots, c_{2^N - 1}$ as follows and print it $\bmod 998{,}244{,}353$.

$c_k = \sum_{i, j, i \& j = 0, i | j = k} a_i b_j$

We note that $i \& j, i | j$ mean bitwise-AND, bitwise-OR.

$c_k = \sum_{i, j, i \& j = 0, i | j = k} a_i b_j$

ただし $i \& j, i | j$ はそれぞれbitwise-AND, bitwise-ORとします

## Constraints制約

• $0 \leq N \leq 20$
• $0 \leq a_i < 998{,}244{,}353$
• $0 \leq b_i < 998{,}244{,}353$

## Input入力

$N$
$a_0$ $a_1$ ... $a_{2^N - 1}$
$b_0$ $b_1$ ... $b_{2^N - 1}$


## Output出力

$c_0$ $c_1$ ... $c_{2^N - 1}$


## Sampleサンプル

### # 1

3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16

9 28 38 100 58 144 172 408


Timelimit: 10 secs

Before submitting, please confirm terms and conditions