#P18220. Donkey, Keep Watch

Donkey, Keep Watch

Donkey, Keep Watch

Donkey、Shrek 和 Puss in Boots 潜入了仙女教母的魔药工厂。他们没能找到需要的魔药,只能自己调配。

工厂里有 nn 瓶魔药,第 ii 瓶的效力为整数 aia_i。他们需要选取一个非空的魔药子集混合。混合后的魔药具有三个属性:

  • 甜度:所选魔药效力的按位异或(XOR);
  • 香气:所选魔药效力的按位与(AND);
  • 持续时间:所选魔药效力的按位或(OR)。

当且仅当甜度与香气的普通算术和等于持续时间时,得到的是好魔药。求有多少种选择方法,对 109+710^9+7 取模。

换言之,求数组 aa 的非空子序列 ss 中,满足

$$\operatorname{XOR}(s)+\operatorname{AND}(s)=\operatorname{OR}(s)$$

的个数。按下标选择;即使两瓶魔药效力相同,它们仍是不同的魔药。不要求选择连续的一段。

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

本题只有一组数据。

输出格式

输出一个整数,表示答案对 109+710^9+7 取模的结果。

数据范围

  • 1≤n≤1061\le n\le10^6;
  • 0≤ai≤150000\le a_i\le15000。

样例

5
1 2 3 4 5
11

样例说明

任意选择两瓶魔药都满足条件,共有 1010 种。另外,选择效力为 {1,2,4}\{1,2,4\} 的三瓶也满足条件,因此答案是 1111。

例如 {1,2,4}\{1,2,4\} 的按位或为 77,按位与为 00,按位异或为 77,所以 7+0=77+0=7,能调配出好魔药。