406563: GYM102441 E Very Simple Sum

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Very Simple Sumtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

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

加入题单

上一题 下一题 算法标签: