Problem Description

You can write integers between $ 1 $ and $ T $ (inclusive) on a blackboard, with each $ i $ written at most $ a_{i} $ times.

You can repeatedly perform the following operation on the written integers until only one integer remains on the blackboard:

• Choose an integer $ X $ that appears at least twice on the blackboard, erase two instances of $ X $, and write one instance of $ X+1 $ on the blackboard.

How many ways are there to write the integers such that you can achieve this goal?

Since the answer can be very large, compute it modulo $ 1000000007 $.

Two ways of writing the integers are considered different if there exists an integer that is written a different number of times in each of the two ways before starting the operations.

Input Format

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

$ T $ $ a_1 $ $ a_2 $ ... $ a_{T-1} $ $ a_T $

Output Format

Output the number of ways to write the integers such that you can reduce them to one integer through the operations, modulo $ 1000000007 $.

Sample Input and Output

Sample Input #1

2
1 1

Sample Output #1

2

Sample Input #2

3
2 1 1

Sample Output #2

6

Sample Input #3

8
300 300 300 300 300 300 300 300

Sample Output #3

220439161

Notes/Hints

Constraints

• $1 \leq T \leq 300$
• $0 \leq a_i \leq 300$
• All inputs are integers.

Sample Explanation 1

Writing one $ 1 $ or one $ 2 $ satisfies the condition.

见题面 Input 部分

见题面 Output 部分