부분집합 합성곱

크기가 $2^N$인 정수 수열 $a_0, a_1, \dots, a_{2^N - 1}$과 $b_0, b_1, \dots, b_{2^N - 1}$가 주어진다. 다음과 같이 정수 수열 $c_0, c_1, \dots, c_{2^N - 1}$을 계산하고 이를 $\bmod 998244353$ 출력한다.

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

$i \And j, i | j$는 비트 단위-AND, 비트 단위-OR를 의미한다는 점에 유의하라.

제약 조건

• $0 \leq N \leq 20$
• $0 \leq a_i < 998244353$
• $0 \leq b_i < 998244353$

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

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