Counting Possible Match Outcomes in a Football League

In a recent football league, N teams participated and each pair of teams played exactly one match. The rules for each match are as follows:

• If the match ends in a draw, both teams are awarded 1 point.
• If one team wins, the winner is awarded 3 points and the loser 0 points.

MoMo loves watching football but missed the recent league while getting engrossed in an archery game. However, by reading the news she learned the final points of each team. Now, she is curious to know in how many different ways the matches could have ended so that the final scores of the teams match the reported totals.

More formally, you are given an integer N and an array of N non-negative integers. The array indicates the final points for each team. Every two teams play exactly one match. In each match, if one team wins, the winning team gains 3 points and the losing team gains 0 points; in case of a draw, both teams gain 1 point. Your task is to count the number of possible match outcome assignments that yield the given final scores. Since the answer may be very large, output it modulo \(10^9+7\).

Note: If there is no possible match outcome assignment that results in the given final scores, output 0.

inputFormat

The first line contains a single integer N indicating the number of teams. The second line contains N non-negative integers, where the i-th integer represents the final points of the i-th team.

It is guaranteed that the input is valid and that the number of teams is small enough for a backtracking solution with memoization to run in reasonable time.

outputFormat

Output a single integer: the number of possible match outcome assignments that yield the given final scores, taken modulo \(10^9+7\).

sample

3
3 3 3

2