HZNUOJ

小Q的异或

Tags:   水题
Time Limit:  50 s      Memory Limit:   1024 MB
Submission:186     AC:31     Score:99.22

Description

给一个长度为$n$的正整数序列$a_1, \cdots, a_n$:
请计算:
$$
\begin{eqnarray*}
\sum\limits_{i = 1}^{n - 2} \sum\limits_{j = i + 1}^{n - 1} \sum\limits_{k = j + 1}^n (a_i \oplus a_j)(a_j \oplus a_k)(a_i \oplus a_k) \bmod 998244353
\end{eqnarray*}
$$
此处$\oplus$的含义为按位异或。

Input

单组数据评测。
第一行一个正整数$n(3 \leq n \leq 10^5)$,表述序列的长度。
第二行$n$个正整数$a_i(1 \leq a_i \leq 10^9)$,表示序列中第$i$个数。

Output

输出包含一行一个正整数表示答案。

Samples

input
3 1 2 3
output
6

Author

PAN, Lyuzhi