#3139. [Hnoi2013]比赛

内存限制:128 MiB 时间限制:20 Sec

题目描述

沫沫非常喜欢看足球赛,但因为沉迷于射箭游戏,错过了最近的一次足球联赛。此次联 赛共N支球队参加,比赛规则如下:
(1) 每两支球队之间踢一场比赛。 (2) 若平局,两支球队各得1分。
(3) 否则胜利的球队得3分,败者不得分。
尽管非常遗憾没有观赏到精彩的比赛,但沫沫通过新闻知道了每只球队的最后总得分, 然后聪明的她想计算出有多少种可能的比赛过程。
譬如有3支球队,每支球队最后均积3分,那么有两种可能的情况:
 可能性1    可能性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
但沫沫发现当球队较多时,计算工作量将非常大,所以这个任务就交给你了。请你计算 出可能的比赛过程的数目,由于答案可能很大,你只需要输出答案对109+7取模的结果

输入格式

第一行是一个正整数N,表示一共有N支球队。 接下来一行N个非负整数,依次表示各队的最后总得分。

输入保证20%的数据满足N≤440%的数据满足N≤660%的数据满足N≤8100%的数据 满足3≤N≤10且至少存在一组解。

输出格式

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

样例

样例输入


			
4
4 3 6 4

样例输出


			
3

数据范围与提示