Problem H
Nim Cheater
After solving all of the problems in an ACM contest perfectly, Dai and Long celebrated their victory by a trip to Stonehenge! At Stonehenge, Dai and Long not only saw a huge henge but also discovered $N$ heaps of stones! Those heaps contain $a_1, a_2, \ldots , a_ N$ small stones, respectively. The two students played the game of Nim with the heaps. In the standard Nim game, two players take alternating turns. At each turn the player has to choose a heap with at least one remaining stone and then remove at least one stone from it. The player can remove a whole heap as well. The player who removes the last stone from the last remaining heap wins the game.
Long was very angry with Dai since Dai had made so many incorrect submissions during the programming contest. That’s why, while pretending to be friendly with Dai by leaving him the first move, Long plans to stealthily remove one or more stones from some heaps so that Dai would surely lose the game no matter how clever he is. However, in order to avoid being detected, Long must leave at least two heaps unchanged.
Given $N$ and the number of stones in each heap, your task is to calculate the number of ways Long can remove stones from at most $N - 2$ heaps, so that Dai (acting as the player moving first) loses the game no matter how he plays.
Input
-
The first line of the input contains an integer $N$ ($2 \leq N \leq 1\, 000$) – the number of heaps.
-
The second line contains $N$ integers $a_1, a_2,\ldots , a_ N$ ($1 \leq a_ i \leq 10^{18}$) – the number of stones in each heap.
Output
Output the number of possible ways Long can remove stones, modulo $10^9+7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 5 6 |
3 |
