A Zero Xor Subset is a non-empty subset having Xor of all the elements in it equal to 0.
Now you are given an array of N numbers.
You have to count the number of different Zero Xor Subsets of this array.

Input:
First line contains a number N
N is the length of the array.
Second line contains the N elements of the array.

Output:
Single number denoting the Count of Zero Xor Subsets of the given array.

Input Constraints:
1<=N<=40
1<=a[i]<=10¹⁸

Hint:

Meet in the middle