[HNOI2013]比赛
题号：NC20103
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联 赛共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
3
 -
 0
 3
C
 3
 0
 -
 3
0
 3
 -
 3
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算 出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对10^9+7取模的结果











输入描述:

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

输出描述:

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

输入

复制 
4
4 3 6 4

输出

复制 
3

备注:

20%的数据满足;

40%的数据满足;

60%的数据满足;

100%的数据满足且至少存在一组解。