Gukiz is obsessed with binary operations. He is trying to solve a task with the binary operation XOR, but he can’t seem to figure out one problem. Can you help?

You are given an array a with n elements. Calculate the number of ways to split this array into 2 disjoint non-empty groups with equal XOR value between their elements.

A disjoint group means that each element of array a is located in exactly 1 group. The answer can be very large, so print it by modulo (109+7).

Input Format

The first line of input contains one integer n: the size of array a. The second line contains nseparated integers a1,a2,…,an, representing array a.

Constraints:

1≤n≤105
0≤ai≤109

Note: The scoring for this problem is binary. You have to pass all the testcases to get a positive score.

Output Format

In a single line, print one integer - number of ways for splitting the array into two groups with equal XOR by modulo 109+7.

Sample Input 1

3
0 1 1

Sample Output 1

3

Sample Input 2

4
5 2 3 2

Sample Output 2

0

Explanation

In the first example, we have array a with three elements a={0,1,1}. We can split this array in the following ways:

1. {1,1},{0}. The XOR of the first group is equal to 0 (1 XOR 1 = 0). The XOR of the second group is equal to 0.
2. {0,1}, {1}. The XOR of the first and second group is equal to 1.
3. {0,1}, {1}. Same case as above.

We have two ones, so we have two possible groups {0,1}. Answer is 3.

In the second example, we cannot split the array. Answer is 0.

Note: The xor operator exists in most programming languages, for example, in C++, Java and Python xor is represented as ^, in Pascal — as xor.

his is a trick question.

If you have integers a1...an and you can divide them into two parts such that their XORs are equal, this just means that a1 xor a2 xor ... xor an equals zero. When that holds, ANY partition works, e.g. (a1) xor (a2 xor a3 xor ... xor an) == 0 by the above, so it must be that a1 == a2 xor ... xor an. Hence ANY partition works. Given that, you just either select an empty partition and full partition, if that is allowed, or the smallest integer into a singleton partition and put everything else into the second one.

Lets us suppose the xor of subset 1 is X1 and that of subset 2 is X2 

now given X1=X2 which implies X1^X2 =0 that means a1^a2^a^3.....=0;

therefore we can choose any partition of the array given on the constraint that is(it must contain a single element to derive our forumla)

How 2^n-2/2

let us construct subset A thereby B is constructed automatically from the reamining elements of the array 

 the number of ways to select elements for set A are

let Q=

 nc1+ cn2+........ncn-1  (considering we have to choose 1 elem atleast)

Now we know

nc0+ nc1+ nc2+.....+nCn=pow(2,n)

therefore 

Q=2^n-2

now we notice that halfway through we have doubly computed our answers as set A and set B are not ordered pairs therefore we divide the result by 2.

Code

#include<iostream>
#include<stdio.h>

using namespace std;

const int m=1e9+7;
const int maxN=1e6;

int x,xs,n,st[maxN];

int main()
 {
   scanf("%d\n",&n);

   xs=0; 
   st[0]=1;
   for (int i=1;i<n;i++)
   st[i]=(st[i-1]*2)%m;


   for (int i=0;i<n;i++)
   {
       scanf("%d",&x);
       xs=xs^x;
   }

   if (xs!=0) printf("%d",0); else
       printf("%d",(st[n-1]+m-1)%m);

   return 0;
}