Alice and Bob are playing the game of Nim with piles of stones with sizes . If Alice plays first, she loses if and only if the 'xor sum' (or 'Nim sum') of the piles is zero, i.e., .
Since Bob already knows who will win (assuming optimal play), he decides to cheat by removing some stones in some piles before the game starts. However, to reduce the risk of suspicion, he must keep at least one pile unchanged. Your task is to count the number of ways Bob can remove the stones to force Alice into losing the game. Since the number can be very large, output the number of ways modulo . Assume that both players will try to optimize their strategy and try to win the game.
Input Format
The first line of the input contains an integer denoting the number of piles. The next line contains space-separated integers indicating the sizes of the stone piles.
Constraints
Output Format
Print a single integer denoting the number of ways Bob can force Alice to lose the game, modulo .
Sample Input 0
3
1 2 3
Sample Output 0
4
Explanation 0
The answer is . The four possible resulting lists of piles is:
Note that is not allowed since he must keep one pile unchanged.
Sample Input 1
10
10 10 1 1 1 1 1 10 10 10
Sample Output 1
321616