驴子，看好药水

驴子、史莱克和穿靴子的猫潜入了神仙教母的药水工厂，试图寻找一种能解决食人魔婚姻问题的药水。然而，他们没能找到这样的药水，所以他们必须自己调制。

工厂里有 $n$ 瓶药水，第 $i$ 瓶药水的效力为 $a_i$。他们必须选择一个非空的药水子集进行混合，以调制出一种“好药水”。这种新药水具有以下特性：

• 其甜度，计算方法为混合中所有药水效力的按位异或（XOR）值。
• 其香气，计算方法为混合中所有药水效力的按位与（AND）值。
• 其持续时间，计算方法为混合中所有药水效力的按位或（OR）值。

当且仅当药水的甜度与香气之和等于其持续时间时，该药水才被称为“好药水”。你需要计算史莱克和他的朋友们调制出好药水的方法数。

换句话说，求 $a$ 的非空子序列 $s$ 的数量，使得 $\text{XOR}(s) + \text{AND}(s) = \text{OR}(s)$。

输入格式

第一行包含一个整数 $n$ —— 可用药水的数量。 第二行包含 $n$ 个整数 —— 药水的效力。

数据范围

$1 \le n \le 10^6$ $0 \le a_i \le 15 \cdot 10^3$

输出格式

输出一个整数 —— 调制好药水的不同方法数。由于该数字可能很大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

11

说明

在样例中，调制好药水的方法是选取以下药水子集：$\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{3, 4\}, \{3, 5\}, \{4, 5\}$ 以及 $\{1, 2, 4\}$，总共 11 种。 例如，如果我们选取集合 $\{1, 2, 4\}$，其按位或（OR）为 7，按位与（AND）为 0，按位异或（XOR）为 7，由于 $0 + 7 = 7$，这确实得到了一种好药水。