disjoint-groups

You are given a list L with n items. Find the number of ways to split this list into two disjoint non-empty groups with equal XOR value between their items.

A disjoint group means that each item of a  list L is located in exactly one group. 

The answer can be very large, so print it by modulo (10^9+7).

Input
First line of input contains one integer n which denotes  the size of list L. 

Second line contains n space separated integers enter code hereL1,L2,…,Ln, representing items in the list L.

Output
In each line corresponding to input print one integer (i.e., answer) - number of ways for splitting the list into two groups with equal XOR by modulo 10^9+7.

Constraints
1 ≤ n ≤ 10^5

0 ≤ Li ≤ 10^9

SAMPLE INPUT
3
4 0 4

SAMPLE OUTPUT
3

Explanation

We have list L with three elements L = {4,0,4}. 

We can split this list in the following three ways: 
{4,0},{4}. The XOR of the first group is equal to 4 (4 XOR 0 = 4). The XOR of the second group is equal to 4 and so XOR of 4 and 4 is 0.
{4,4},{0}. The XOR of the first group is equal to 0 (4 XOR 4 = 0). The XOR of the second group is equal to 0.
{0,4},{4} same as 1.

We have two fours, so we have 2 possible groups  of {0,4}.

Therefore the Answer is 3.

Source: hackerearth | Difficulty: MEDIUM


Solutions: