We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 1
  3. XOR Groups

XOR Groups

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

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

A group means that each element of array is located in exactly 1 group. The answer can be very large, so print it by modulo .

Input Format

The first line of input contains one integer : the size of array . The second line contains separated integers , representing array .

Constraints:


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 by modulo .

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 with three elements . We can split this array in the following ways:

  1. ,. The of the first group is equal to ( XOR = ). The of the second group is equal to .

  2. , . The of the first and second group is equal to 1.

  3. , . Same case as above.

We have two ones, so we have two possible groups . Answer is .

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

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