Problem Description

Mr. Takahashi has $ N $ legs, and the $ i $th leg consists of $ L_i $ bones connected in a row. All the ends of the legs are connected to Mr. Takahashi's body, which has no bones.

Mr. Takahashi has decided to write a character, either $ 0 $ or $ 1 $, on every bone of all his legs.

Mr. Takahashi has strong preferences for how the characters should be written. For any two different legs $ A $ and $ B $, he is satisfied only if the sequence of characters written on the bones from the end of $ A $ not connected to the body to the end of $ B $ not connected to the body, via the body, forms a palindrome.

Find the number of ways Mr. Takahashi can write the characters to satisfy his requirement, modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ L_1 $ . . . $ L_N $

• The first line contains an integer $N(1\ ≦\ N\ ≦\ 100000)$, representing the number of Mr. Takahashi's legs.
• The following $ N $ lines contain integers $L_i(1\ ≦\ L_i\ ≦\ 10^9)$, representing the length of the $ i $th leg.

Output Format

Output a single integer representing the number of ways Mr. Takahashi can write the characters to satisfy his requirement, modulo $ 10^9+7 $.

Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
2
4
8

Sample Output #1

8

Sample Input #2

8
2
1
4
3
6
5
8
7

Sample Output #2

4

Sample Input #3

5
700000000
20000000
9000000
600000000
30000000

Sample Output #3

861838989

Notes/Hints

Sample Explanation 1

Writing the strings on the three legs from the end not connected to the body, examples like $ (01,0111,01111111) $ satisfy the condition.

见题面 Input 部分

见题面 Output 部分