Background

GZOI2017 D1T1

Problem Description

Alice and Bob are playing an ancient game. There are several piles of stones. Alice and Bob take turns to take stones. Each time, a player may choose one pile and take any number of stones from it, but they must take at least one stone. Whoever takes the last stone so that the other player cannot move wins.

Now there are $N$ piles of stones on the field, numbered from $1$ to $N$. Alice quickly discovered that this game has some fixed strategies. Cunning Alice wants to win this match, so she comes to you, the organizer, and asks you to select some piles from these $N$ piles as the piles used in the final game, such that Alice can win. Of course you do not want Alice to succeed, so you propose a condition: the pile that Alice takes from in her first move must be designated by you (you only designate the pile index, not how many stones she takes). This designated pile must be included among the piles chosen for the final game.

Now you are curious and want to compute how many different plans make it impossible for Alice to win. Note that even if the set of chosen pile indices is exactly the same, plans are still considered different if the designated pile index for the first move is different.

Input Format

The first line contains a positive integer $N$, denoting the number of piles.

The second line contains $N$ positive integers, denoting the number of stones in each pile, given in order from pile $1$ to pile $N$.

Output Format

Output one line containing the number of plans. The answer should be taken modulo $10^9+7$.

3
2 4 5

5

3
1 2 2

6

Hint

[Sample $1$ Explanation]

The first plan: choose piles $1$ and $2$, and designate pile $1$.

The second plan: choose piles $1$ and $3$, and designate pile $1$.

The third plan: choose piles $1$, $2$, and $3$, and designate pile $2$.

The fourth plan: choose piles $1$, $2$, and $3$, and designate pile $3$.

The fifth plan: choose piles $2$ and $3$, and designate pile $2$.

[Constraints]

Translated by ChatGPT 5