题目描述
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.
输入格式
见题面
输出格式
见题面