Problem 6184 --NOI2013湖北省选 一试 第1题 比赛

6184: NOI2013湖北省选 一试 第1题 比赛

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 5  Solved: 3
[Submit][Status][Web Board][Creator:][下载FPS2元][添加到购物车][下载测试数据2元][92kb]

Description

沫沫非常喜欢看足球赛,但因为沉迷于射箭游戏,错过了最近的一次足球联赛。此次联
赛共N 支球队参加,比赛规则如下:
(1) 每两支球队之间踢一场比赛。
(2) 若平局,两支球队各得1 分。
(3) 否则胜利的球队得3 分,败者不得分。
尽管非常遗憾没有观赏到精彩的比赛,但沫沫通过新闻知道了每只球队的最后总得分,
然后聪明的她想计算出有多少种可能的比赛过程。

譬如有3 支球队,每支球队最后均积3 分,那么有两种可能的情况:

但沫沫发现当球队较多时,计算工作量将非常大,所以这个任务就交给你了。请你计算
出可能的比赛过程的数目,由于答案可能很大,你只需要输出答案对109+7 取模的结果。

Input

第一行是一个正整数N,表示一共有N支球队。
接下来一行N个非负整数,依次表示各队的最后总得分。
输入保证20%的数据满足N≤4,40%的数据满足N≤6,60%的数据满足N≤8,100%的数据
满足3≤N≤10且至少存在一组解。

Output

仅包含一个整数,表示答案对109+7 取模的结果。

Sample Input

4
4 3 6 4

Sample Output

3

HINT

Source

[Submit][Status]