Description

Momo loves watching soccer matches, but she missed the latest league because she was addicted to an archery game. There are $N$ teams in the league, and the rules are as follows:

1. Every pair of teams plays exactly one match.
2. If a match ends in a draw, each team gets $1$ point.
3. Otherwise, the winner gets $3$ points and the loser gets $0$ points.

Although she could not watch the exciting matches, Momo learned from the news the final total points of each team. Now she wants to compute how many possible tournament outcomes are consistent with these totals.

For example, if there are $3$ teams and each team finishes with $3$ points, then there are two possibilities:

Possibility $1$ and Possibility $2$

Since the answer can be large, output it modulo $10^9+7$.

Input Format

The first line contains a positive integer $N$, the number of teams.
The second line contains $N$ non-negative integers, giving the final total points of each team in order.

Output Format

Output a single integer, the answer modulo $10^9+7$.

4
4 3 6 4

3

Hint

• $20\%$ of the testdata satisfies $N \le 4$.
• $40\%$ of the testdata satisfies $N \le 6$.
• $60\%$ of the testdata satisfies $N \le 8$.
• $100\%$ of the testdata satisfies $3 \le N \le 10$, and there exists at least one solution.

Translated by ChatGPT 5