E. Very Simple Sum
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$, each consisting of $$$n$$$ integers. Your task is to calculate a very simple sum: $$$$$$ \sum_{1 \le x \le n} \sum_{1 \le y \le n} \sum_{1 \le z \le n} \sum_{1 \le w \le n} (a_x + a_y + a_z + a_w)^{(b_x \oplus b_y \oplus b_z \oplus b_w)} \mod 998244353 $$$$$$

Input

First line contains a single integer $$$n$$$ — the number of elements in arrays $$$a$$$ and $$$b$$$.

Second line contains $$$n$$$ space-separated integers $$$a_i$$$ — the elements of the array $$$a$$$.

Third line contains $$$n$$$ space-separated integers $$$b_i$$$ — the elements of the array $$$b$$$. $$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le a_i, b_i \le 500$$$$$$

Output

Output a single integer  — the value of the very simple sum.

Examples
Input
1
1
1
Output
1
Input
5
227 67 445 67 213
297 171 324 493 354
Output
42