题目描述

塔子哥有一个长度为 $n$ 的数组 $a$ 。

他对一个数组的权值定义为，这个数组中两个不同的不同下标 $i,j(0\leq i<j<n)$ ，所有 $a_i\ xor\ a_j$ 的和。
即 $\sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1} a_i\ xor\ a_j$ 。

现在塔子哥想要问你，这个数组的所有连续子数组的权值之和是多少。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示数组的长度。
第二行，$n$ 个整数，第 $i$ 个整数为 $a_i(1 \leq a_i \leq 10^9)$ 。

输出描述

一个整数，表示所有子数组的权值之和，答案对 $10^9+7$ 取模

样例

输入

3
1 2 3

输出

10

说明

对于子数组 $a[1,2]$ 来说，权值为 $3$
对于子数组 $a[2,3]$ 来说，权值为 $1$
对于子数组 $a[1,2,3]$ 来说，权值为 $6$
$3+1=6=10$