题目描述

即墨市计算机职业技术学院的小 w 在数据结构课上学完了位运算，为了证明他的实力比小 z 强，他随手给小 z 出了个题。

问题如下： 给你一个序列 $a_{i}$，算出下列式子

$\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{k = 1}^{n}\sum_{d = 1}^{n}(a_{i} \text{ or }a_{j})xor(a_{k}\text{ and }a_{d})$

，并且答案给对$2^{32}$取模。

小 z 遇到了困难，请你来帮助他。

输入格式

第一行一个正整数 $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

提示

对于 $20\%$ 的数据 $n \le 80$

对于另外 $20\%$ 的数据 $0\le a_{i} \le 80$

对于另外$20\%$的数据 $0 \le a_{i} \le 5000$

对于另外 $20\%$ 的数据 $n \le 1000$

对于 $100\%$ 的数据 $n \le 5 \cdot 10^5，0 \le a_i \le 2^{32}-1$