题面

给定一个有个 n 元素的数组 a,请你求出这个数组的所有 非空子序列 的“幸运值”之和 对1e9+7取模后的结果。

一个子序列的"幸运值"定义为 : 该子序列中所有元素按位与(AND)结果的二进制表示中1的个数。

输入

第一行输入一个正整数n，(1 <= n <= 1e6),表示数组中元素数量，接下来又n个正整数，a[1],a[2],a[3],...,a[n] (0 <= a[i] <= 1e6)

输出

输出一个数，表示这个数组的幸运值。

示例1

2
2 3

4

示例1解释：

子序列{2}的AND值为1(二进制10),有1个1;

子序列{3}的AND值为2(二进制11),有2个1；

子序列{2,3}的AND值为2&3=2(二进制10),有1个1；

总和为1+2+1=4。

限制

1s, 1024KiB for each test case.