돌 게임

Nim 게임을 들어본 적 있을 것이다. 하지만 "Steins;Game"이라는 새로운 게임은 들어본 적이 없을 것이다. 이 게임은 여러 개의 돌 더미로 하는 게임이라서 이런 이름이 붙었다. Stein은 독일어로 돌이라는 뜻이다.

Alice와 Bob이 이 게임을 하려고 한다. 게임은 다음과 같이 진행된다.

돌 더미 $n$개가 일렬로 놓여 있다. 각 더미는 흰색 또는 검은색으로 칠해져 있다. $i$번째 더미에는 $a_i$개의 돌이 있다. Alice부터 시작해서 두 사람이 번갈아 가며 다음 중 하나를 한다.

• 가장 작은 검은 더미(모든 검은 더미 중 가장 작은 것)에서 양의 개수만큼 돌을 가져간다. 또는
• 임의의 흰색 더미에서 양의 개수만큼 돌을 가져간다.

돌이 모두 없어지면 게임이 끝난다. 다음 수를 두는 사람이 게임에서 진다.

이제 모든 더미의 돌 개수는 정해졌지만, 아직 색은 칠하지 않았다. Bob은 심판을 매수해서 모든 더미를 직접 칠할 기회를 얻었다. Alice와 Bob이 최선을 다해 플레이할 때 Bob이 이길 수 있도록 더미를 칠하는 방법이 몇 가지인지 구하라. 답이 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력하라.

첫 줄에 게임에 있는 돌 더미의 개수 $n$ $(1\leq n\leq 10^5)$이 주어진다.

둘째 줄에는 $n$개의 정수 $a_1,a_2,\cdots,a_n$ $(1\leq a_i\leq 10^{18})$이 주어진다. 각 더미에 들어 있는 돌의 개수이다.

Bob이 이길 수 있도록 더미를 칠하는 방법의 수를 한 줄에 출력한다. 답은 $1\,000\,000\,007$로 나눈 나머지이다.

첫 번째 테스트 케이스에서는 더미를 칠하는 네 가지 방법 중 어느 것을 택하더라도 Bob이 이긴다.

두 번째 테스트 케이스에서 Bob이 이길 수 있는 유일한 방법은 두 더미를 모두 검은색으로 칠하는 것이다. 그러면 Alice는 첫 수에 첫 번째 더미를 가져갈 수밖에 없고, Bob이 두 번째 더미 전체를 가져가서 이긴다.

세 번째 테스트 케이스에서는 Bob이 더미를 어떻게 칠하든 Alice가 더미 전체를 가져가서 이긴다.