Kanade's convolution

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

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$

Input

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

Output only one integer means the answer.

Sample Input

2 1 2 3 4 5 6 7 8

Sample Output

568535691

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码