시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 256 MB111100.000%

문제

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 $$

입력

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$.

출력

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

제한

  • $1 \le n \le 10^5$
  • $1 \le a_i, b_i \le 500$

예제 입력 1

1
1
1

예제 출력 1

1

예제 입력 2

5
227 67 445 67 213
297 171 324 493 354

예제 출력 2

42