Donkey, Keep Watch

Обмеження: 4 сек., 512 МіБ

Donkey, Shrek and Puss in Boots have snuck into the Fairy Godmother’s potion factory to find a potion that will solve the ogre’s marital problems. However, they are unable to find such a potion, so they will have to brew one themselves.

In the factory, there are \(n\) potions, with the \(i\)-th potion having potency \(a_i\). They have to choose some non-empty subset of potions to brew together so that they create a good potion. The new potion will have the following characteristics:

• Its sweetness, calculated by taking the bitwise XOR of all potencies of the potions in the brew.

• Its aroma, calculated by taking the bitwise AND of all potencies of the potions in the brew.

• Its duration, calculated by taking the bitwise OR of all potencies of the potions in the brew.

A brew is good if and only if the sum of its sweetness and its aroma is equal to its duration. You need to figure out the number of ways Shrek and his friends can brew a good potion.

In other words, find the number of non-empty subsequences \(s\) of \(a\) such that \(\text{XOR}(s)+\text{AND}(s)=\text{OR}(s)\).

Вхідні дані

The first line of the input contains a single integer \(n\) — the number of potions available.

The second line of the input contains \(n\) integers — the potencies of the potions.

Вихідні дані

Print a single integer — the number of different ways to brew a good potion. Since this number can be large, print it modulo \(10^9+7\).

Обмеження

\(1\leq n\leq 10^6\),

\(0\leq a_i \leq 15 \cdot 10^3\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 2 3 4 5	11

Примітки

In the sample case, the ways to create a good potion are by taking the following subsets of potions: \(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{1,5\}\), \(\{2,3\}\), \(\{2,4\}\), \(\{2,5\}\), \(\{3,4\}\), \(\{3,5\}\), \(\{4,5\}\) and \(\{1,2,4\}\); which is \(11\) in total. For example, if we take the set \(\{1,2,4\}\), the bitwise OR is \(7\), the bitwise AND is \(0\) and the bitwise XOR is \(7\), and since \(0+7=7\), this indeed yields a good potion.