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