Game with stones

Have you ever heard of the Nim game? Most likely, yes. But you have probably never heard of a newer game called "Steins;Game". It is played with many piles of stones, and Stein means stone in German.

Alice and Bob want to play this game. The game is played as follows:

There are $n$ piles of stones arranged in a row. Each pile is colored either white or black. The $i$-th pile has $a_i$ stones. Starting with Alice, the two players take turns doing one of the following:

• take any positive number of stones from the smallest black pile (the smallest one among all black piles); or
• take any positive number of stones from any white pile.

The game ends when no stones remain, and the player who makes the next move loses the game.

All piles of stones are now fixed, but they are not yet colored. Bob has bribed the referee to get the chance to paint all the piles himself. How many ways can he paint the piles so that he wins, assuming Alice and Bob both play optimally? Since the answer may be very large, output it modulo $1\,000\,000\,007$.

The first line contains one integer $n$ $(1\leq n\leq 10^5)$, the number of piles in the game.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ $(1\leq a_i\leq 10^{18})$, the number of stones in each pile.

Print one integer on a line, the number of ways to paint the piles so that Bob wins, modulo $1\,000\,000\,007$.

For the first test case, Bob wins under any of the four ways to paint the piles.

For the second test case, the only way for Bob to win is to paint both piles black. Alice is then forced to take from the first pile on her first move, and Bob takes the whole second pile and wins.

For the third test case, no matter how Bob paints the only pile, Alice takes the whole pile and wins.