Problem Background

GZOI2017 Day 1 Task 1

Problem Description

Alice and Bob are playing an ancient game. There are several piles of stones, and they take turns picking stones. Each turn, a player can take any number of stones from any single pile, but must take at least one. The player who takes the last stone, leaving the other player with no stones to take, wins.

There are $N$ piles of stones on the field, numbered from $1$ to $N$. Alice quickly realizes that there are some fixed strategies in this game. Sneaky Alice wants to win this game and comes to you, the organizer, hoping you can select some of these $N$ piles to be used in the final game, ensuring her victory. You, naturally, do not want Alice to succeed, so you impose a condition: Alice must take her first turn from a pile whose number you specify (you only specify the pile number, not the number of stones taken, and this specified pile must be included in the final game).

Now, you are curious about how many different ways you can arrange the piles such that Alice cannot win. Note that even if the sets of pile numbers selected are identical, specifying a different first pile for Alice to take from counts as a different arrangement.

Input and Output Format

Input Format

The first line contains a single 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 pile $1$ to pile $N$.

Output Format

A single line containing the number of arrangements, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
2 4 5

Sample Output #1

5

Sample Input #2

3
1 2 2

Sample Output #2

6

Notes

Sample 1 Explanation

First: Select piles numbered $1$ and $2$, specify pile $1$.

Second: Select piles numbered $1$ and $3$, specify pile $1$.

Third: Select piles numbered $1$, $2$, and $3$, specify pile $2$.

Fourth: Select piles numbered $1$, $2$, and $3$, specify pile $3$.

Fifth: Select piles numbered $2$ and $3$, specify pile $2$.

Data Constraints

见题面 Input 部分

见题面 Output 部分