Kanade's convolution

Problem Description

Give you two arrays $A[0..2^m-1]$ and $B[0..2^m-1]$. Please calculate array $C[0..2^m-1]$£º

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

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6057