Nim is a famous two-player algorithm game with the following basic rules:
- The game starts with piles of stones indexed from to . Each pile (where ) has stones. The diagram below shows an example:
- The players move in alternating turns. During each move, the current player must remove one or more stones from a single pile.
- The first player who is unable to remove a stone (e.g., a stone can't be removed if all piles are already empty) loses the game.
Alice and Bob decided to add the following special move before starting a game of Nim:
- Alice selects two indices, and , such that .
- Remove all the piles in the between index and index . Note that the number of removed piles can be anywhere from to .
For example, If Alice selects and , the set of piles of the diagram above would look like this:
After Alice makes the special move, Bob starts a game of Nim as its first player. They both play optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.
Given the number of stones in each pile, find the number of ways Alice can select and to ensure she wins the game.
Input Format
There are two lines of input:
- An integer, , denoting the number of piles.
- space-separated integers describing the respective values of .
Constraints
Subtasks
- for of the maximum score.
Output Format
Print the number of ways Alice can select and to ensure she wins the game.
Sample Input 0
3
1 1 2
Sample Output 0
2
Explanation 0
There are piles that look like this:
Alice can remove piles in the following six ways:
- and they are left with one pile of size and one pile of size . The following figure shows that Bob will win the game.
and again they are left with one pile of size and one pile of size . They play the same as in scenario (so Bob wins).
and they're left with two piles, each of size . Bob starts the game by removing stone from either pile, leaving one pile of size . Alice then removes the stone from the last pile and wins.
and they're left with just one pile of size . Bob starts the game by removing both stones and wins.
and they're left with just one pile of size . Bob starts the game by removing the last stone and wins.
and they don't have any piles remaining. Bob is unable to make a move and so Alice wins the game.
Because there are two ways for Alice to win the game, we print as our answer.
Sample Input 1
4
1 2 3 4
Sample Output 1
2