아주 간단한 합

시간 제한3초메모리 제한256 MB

요약

모든 n^4개의 인덱스 사중항에 대해 (a_x+a_y+a_z+a_w)^(b_x xor b_y xor b_z xor b_w)를 998244353으로 나눈 나머지를 구한다. a_i, b_i는 500 이하다.

난이도: 어려움10점 중 9점
유형: 수학, 조합론, 비트 연산, 정수론
정답자: 아직 제출이 없습니다

문제

길이가 $n$ 인 두 배열 $a$ 와 $b$ 가 주어진다. 다음 값을 계산하시오.

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

입력

첫째 줄에 배열의 길이 $n$ 이 주어진다.

둘째 줄에 배열 $a$ 의 원소 $a_i$ 가 $n$ 개 주어진다.

셋째 줄에 배열 $b$ 의 원소 $b_i$ 가 $n$ 개 주어진다.

출력

아주 간단한 합의 값을 $998244353$ 으로 나눈 나머지를 출력한다.

제한

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

예제2

예제 1
입력
```
1
1
1
```
예상 출력
```
1
```

예제 2

입력

5
227 67 445 67 213
297 171 324 493 354

예상 출력