Kanade's convolution

Give you two arrays $A[0..2^m-1]$ and $B[0..2^m-1]$.

Please calculate array $C[0..2^m-1]$：

$$C[k]=\sum_{i~and~j=k}A[i~xor~j]*B[i~or~j]$$

You just need to print $\sum_{i=0}^{2^m-1}C[i]*1526^i ~mod~998244353$

$m<=19$

$0\leq A[i],B[i]< 998244353$

There is only one test case.

The first line consists of one integer $m$.

The second line consists of $2^m$ integers $A[0..2^m-1]$

The third line consists of $2^m$ integers $B[0..2^m-1]$

Output only one integer means the answer.

2

1 2 3 4

5 6 7 8

568535691

2017 Multi-University Training Contest - Team 3