题目背景

在某个谔谔的一天中，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$。

输出格式

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

2
1 2

30

6
1 1 4 5 1 4

3944

7
1 9 1 9 8 1 0

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$ 分）：无特殊限制。

---

友情提示

请注意数据范围。

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