Donkey, Keep Watch#12978

Donkey, Keep Watch

4 seconds
512 megabytes
Very hard

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 potions, with the -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:

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 of such that \text{XOR}(s)+\text{AND}(s)=\text{OR}(s).

Input

The first line of the input contains a single integer — the number of potions available.

The second line of the input contains integers — the potencies of the potions.

1\leq n\leq 10^6,

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

Output

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.

Examples

Example

Loading
Loading

Note

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