[EER2] 谔运算

题目背景

在某个谔谔的一天中,CYJian 做到一道谔运算的谔谔题,CYJian 发现他不会做,于是决心从头开始研究令人谔谔的谔运算。

题目描述

首先,CYJian 写出了一个长度为 $n$ 的数列 $a$。 然后他灵光一动,写出了下面这个谔谔的式子: $$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n} (a_i\ {\rm or}\ a_j)\ {\rm xor}\ (a_k\ {\rm and}\ a_l)$$ CYJian 觉得这个是一个谔运算的简单式子,摁计算器花了 $114514{\rm s}$ 就算出来了答案。 为了证明你吊打 $114514$ 个 CYJian,请你在 $1{\rm s}$ 内算出来这个式子的值吧。你只需要给出答案对 $2^{32}$ 取模的值即可。

输入输出格式

输入格式


第一行一个正整数 $n$ 表示数列的长度。 第二行 $n$ 个非负整数,第 $i$ 个数表示 $a_i$。

输出格式


一行一个非负整数,表示题目描述中给出式子的值。

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

30

输入样例 #2

6
1 1 4 5 1 4

输出样例 #2

3944

输入样例 #3

7
1 9 1 9 8 1 0

输出样例 #3

12892

说明

样例一解释: $(1\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 1) = 0$ $(1\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 2) = 1$ $(1\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 1) = 1$ $(1\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 2) = 3$ $(1\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 1) = 2$ $(1\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 2) = 3$ $(1\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 1) = 3$ $(1\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 2) = 1$ $(2\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 1) = 2$ $(2\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 2) = 3$ $(2\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 1) = 3$ $(2\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 2) = 1$ $(2\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 1) = 3$ $(2\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 2) = 2$ $(2\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 1) = 2$ $(2\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 2) = 0$ 对所有结果求和,即可得到答案为 $30$。 --- **本题采用捆绑测试。** 对于 $100\%$ 的测试点:$1 \leq n \leq 5 \times 10^5$,$0 \leq a_i \leq 2^{32}-1$。 本题共 $6$ 个子任务,各子任务的分值及约定如下: 子任务 $1$($1$ 分):为样例一。 子任务 $2$($14$ 分):$1 \leq n \leq 80$。 子任务 $3$($25$ 分):$0 \leq a_i \leq 80$。 子任务 $4$($30$ 分):$0 \leq a_i \leq 5000$。 子任务 $5$($25$ 分):$1 \leq n \leq 1000$。 子任务 $6$($5$ 分):无特殊限制。 --- #### 友情提示 请注意数据范围。 **如果您不知道上面的谔运算是什么,请参考[这里](https://www.luogu.com.cn/paste/oe4a9czd)**。