Mo loves watching football matches, but because she was addicted to an archery game, she missed the most recent football league. A total of $N$ teams participated in this league, and the rules were as follows:
- Every two teams played one match against each other.
- In the event of a draw, both teams received 1 point.
- Otherwise, the winning team received 3 points, and the losing team received 0 points.
Although she regretted not being able to watch the exciting matches, Mo learned the final total score of each team from the news. Being clever, she wanted to calculate how many possible match outcomes could have led to these scores.
For example, if there are 3 teams and each team finishes with 3 points, there are two possible scenarios:
| Team | A | B | C | Score |
|---|---|---|---|---|
| A | - | 3 | 0 | 3 |
| B | 0 | - | 3 | 3 |
| C | 3 | 0 | - | 3 |
| Team | A | B | C | Score |
|---|---|---|---|---|
| A | - | 0 | 3 | 3 |
| B | 3 | - | 0 | 3 |
| C | 0 | 3 | - | 3 |
However, Mo found that when there are many teams, the calculation becomes very large, so she has handed this task to you. Please calculate the number of possible match outcomes. Since the answer may be very large, you only need to output the result modulo $10^9+7$.
Input
The first line of the input contains a positive integer $N$, representing the total number of teams.
The next line contains $N$ non-negative integers, representing the final total scores of each team in order.
Output
Output the number of possible match outcomes modulo $10^9+7$.
Examples
Input 1
4 4 3 6 4
Output 1
3
Subtasks
$20\%$ of the data satisfies $N \le 4$.
$40\%$ of the data satisfies $N \le 6$.
$60\%$ of the data satisfies $N \le 8$.
$100\%$ of the data satisfies $3 \le N \le 10$ and at least one solution exists.