Alice and Bob are playing an ancient game. There are several piles of stones, and Alice and Bob take turns removing any number of stones from a chosen pile, but they must remove at least one stone. The player who makes the last move, leaving the other player with no stones to take, wins.

There are $N$ piles of stones on the field, numbered $1$ to $N$. Alice quickly discovered that this game has a fixed strategy. The devious Alice wants to win this game, so she comes to you, the organizer, hoping that you will select a subset of these $N$ piles to be used in the final game such that Alice can win. You naturally do not want Alice to succeed, so you propose a condition: you will specify the index of the pile from which Alice must make her first move (you only specify the index of the pile, not how many stones she must take; the specified pile must be included in the subset of piles chosen for the game).

Now you are curious: you want to calculate how many ways there are for Alice to be unable to win. Note that even if the set of indices of the chosen piles is identical, different specified indices for the first move are considered different schemes.

Input

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

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

Output

A single line representing the number of schemes. The answer should be taken modulo $10^9+7$.

Examples

Input 1

3
2 4 5

Output 1

5

Note 1

Scheme 1: Choose piles $1$ and $2$, specify pile $1$.

Scheme 2: Choose piles $1$ and $3$, specify pile $1$.

Scheme 3: Choose piles $1$, $2$, and $3$, specify pile $2$.

Scheme 4: Choose piles $1$, $2$, and $3$, specify pile $3$.

Scheme 5: Choose piles $2$ and $3$, specify pile $2$.

Input 2

3
1 2 2

Output 2

6

Subtasks