#P6102. [EER2] 谔运算

[EER2] 谔运算

题目背景

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

题目描述

首先,CYJian 写出了一个长度为 nn 的数列 aa

然后他灵光一动,写出了下面这个谔谔的式子:

$$\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 觉得这个是一个谔运算的简单式子,摁计算器花了 114514s114514{\rm s} 就算出来了答案。

为了证明你吊打 114514114514 个 CYJian,请你在 1s1{\rm s} 内算出来这个式子的值吧。你只需要给出答案对 2322^{32} 取模的值即可。

输入格式

第一行一个正整数 nn 表示数列的长度。

第二行 nn 个非负整数,第 ii 个数表示 aia_i

输出格式

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

2
1 2

30

6
1 1 4 5 1 4

3944

7
1 9 1 9 8 1 0

12892

提示

样例一解释:

(1 or 1) xor (1 and 1)=0(1\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 1) = 0

(1 or 1) xor (1 and 2)=1(1\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 2) = 1

(1 or 1) xor (2 and 1)=1(1\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 1) = 1

(1 or 1) xor (2 and 2)=3(1\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 2) = 3

(1 or 2) xor (1 and 1)=2(1\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 1) = 2

(1 or 2) xor (1 and 2)=3(1\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 2) = 3

(1 or 2) xor (2 and 1)=3(1\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 1) = 3

(1 or 2) xor (2 and 2)=1(1\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 2) = 1

(2 or 1) xor (1 and 1)=2(2\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 1) = 2

(2 or 1) xor (1 and 2)=3(2\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 2) = 3

(2 or 1) xor (2 and 1)=3(2\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 1) = 3

(2 or 1) xor (2 and 2)=1(2\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 2) = 1

(2 or 2) xor (1 and 1)=3(2\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 1) = 3

(2 or 2) xor (1 and 2)=2(2\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 2) = 2

(2 or 2) xor (2 and 1)=2(2\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 1) = 2

(2 or 2) xor (2 and 2)=0(2\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 2) = 0

对所有结果求和,即可得到答案为 3030


本题采用捆绑测试。

对于 100%100\% 的测试点:1n5×1051 \leq n \leq 5 \times 10^50ai23210 \leq a_i \leq 2^{32}-1

本题共 66 个子任务,各子任务的分值及约定如下:

子任务 1111 分):为样例一。

子任务 221414 分):1n801 \leq n \leq 80

子任务 332525 分):0ai800 \leq a_i \leq 80

子任务 443030 分):0ai50000 \leq a_i \leq 5000

子任务 552525 分):1n10001 \leq n \leq 1000

子任务 6655 分):无特殊限制。


友情提示

请注意数据范围。

如果您不知道上面的谔运算是什么,请参考这里