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

liuyiding

## Source

2017 Multi-University Training Contest - Te