沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联赛共 $N$ 支球队参加，比赛规则如下：
- 每两支球队之间踢一场比赛。
- 若平局，两支球队各得 1 分。
- 否则胜利的球队得 3 分，败者不得分。
尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分，然后聪明的她想计算出有多少种可能的比赛过程。
譬如有 3 支球队，每支球队最后均积 3 分，那么有两种可能的情况：
| 球队 | A | B | C | 得分 |
|---|---|---|---|---|
| A | - | 3 | 0 | 3 |
| B | 0 | - | 3 | 3 |
| C | 3 | 0 | - | 3 |
| 球队 | A | B | C | 得分 |
|---|---|---|---|---|
| A | - | 0 | 3 | 3 |
| B | 3 | - | 0 | 3 |
| C | 0 | 3 | - | 3 |
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。
输入格式
输入文件第一行是一个正整数 $N$，表示一共有 $N$ 支球队。
接下来一行 $N$ 个非负整数，依次表示各队的最后总得分。
输出格式
样例数据
样例输入
4 4 3 6 4
样例输出
3
子任务
输入保证 $20\%$ 的数据满足 $N \le 4$，
$40\%$ 的数据满足 $N \le 6$，
$60\%$ 的数据满足 $N\le 8$，
$100\%$ 的数据满足 $3 \le N \le 10$ 且至少存在一组解。