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 (109+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 109+7.
Constraints
1 <= n <= 105
0 <= Li <= 109
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.
