Stonehenge is perhaps the world’s most famous prehistoric monument. It was built in several stages: the first monument was an early henge monument, built about 5,000 years ago, and the unique stone circle was erected in the late Neolithic period about 2500 BC. Today, along with Avebury, it forms the heart of a World Heritage Site, with a unique concentration of prehistoric monuments.
After perfectly solved all problems in an ACM contest, Dai and Long celebrated their victory by a trip to Stonehenge! In Stonehenge, Dai and Long not only saw huge henge but also discovered $N$ heaps of gravel! Those heaps contain $a_1$, $a_2$,…, $a_ N$ pieces of gravels, respectively. The two students played the standard Nim game here. In the standard Nim game, two players take turn alternatively. In each turn the player has to choose one heap with at least one remaining gravel, remove at least one gravel from it. The player can remove a whole heap as well. The player who removes the last gravel from the last remaining heap wins the game.
Long was very angry with Dai since Dai had made so many incorrect submissions during the contests. That’s why, while pretending to be friendly with Dai by leaving him the first move, Long stealthy removed gravel 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 gravel in each heap, your task is to calculate the number of ways Long can remove gravel from at most $N - 2$ heaps, so that Dai (acting as the player moving first) loses the game no matter how he plays.
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$,…, $a_ N$ - the number of gravels in each heap. ($1 \leq a_ i \leq 10^{18}$).
Write the number of possible ways modulo $10^9+7$.
Sample Input 1 | Sample Output 1 |
---|---|
3 4 5 6 |
3 |