Stone Pile Nim Game

Alice and Bob are playing an ancient game with stone piles. Initially, there are N piles of stones numbered from 1 to N. In each move a player may choose any one pile and remove any positive number of stones from that pile. The player who makes a move leaving no legal move for the opponent wins.

Alice has discovered that this game has a fixed‐strategy solution. In order to guarantee her win, she asks the organizers to select a collection of piles (from the given N piles) to be used in the game and, moreover, to designate one pile (which must be among the chosen ones) from which she must make her first move. Note that only the pile index is fixed; the number of stones she removes from that pile is not pre‐specified.

You, however, do not wish to let Alice win. Your task is to count the number of ways to choose a nonempty subset S of piles and to designate one pile d (with d ∈ S) for her first move such that no matter what move she makes from pile d, she will never be able to force a win. Two schemes are considered different if either the chosen subset differs or the designated pile is different.

It can be shown that a necessary and sufficient condition for Bob (the opponent) to be able to force a win is that the configuration satisfies

\( \bigoplus_{i\in S} a_i = 1 \)

and the designated pile d must satisfy

\( a_d = 1 \)

Here, \( a_i \) denotes the initial number of stones in pile i and \( \oplus \) is the bitwise XOR operation. This is because when \( a_d = 1 \) the only move from pile d is to remove 1 stone (making it 0), and then the overall XOR becomes

\( \bigl(\bigoplus_{i\in S} a_i\bigr) \oplus a_d \oplus 0 = 1 \oplus 1 = 0\),

which is a losing position for the next player in normal play. For any pile with more than one stone, Alice would have several move choices, at least one of which might not yield a losing position. Therefore, the game scheme is safe for Bob if and only if the following conditions hold:

• The XOR of stone counts of all chosen piles is 1, i.e., \( \bigoplus_{i\in S} a_i = 1 \).
• The designated pile has exactly one stone, i.e., \( a_d = 1 \).

You are given the stone counts of all N piles. Count the number of schemes (choice of nonempty subset S of piles and a designated pile d with \( a_d = 1 \) in S) that satisfy the above conditions.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 50), the number of stone piles.
The second line contains N positive integers \(a_1, a_2, \dots, a_N\) where \(1 \le a_i \le 10^9\) representing the number of stones in each pile.

outputFormat

Output a single integer representing the number of schemes such that, if the game is played with the chosen subset and the designated first‐move pile, Alice will not be able to force a win.

sample

3
1 2 3

1