2915: 粉刷匠
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
赫克托是一个魁梧的粉刷匠，而且非常喜欢思考= = 现在，神庙里有 N 根排列成一直线的石柱，从 1 到 N 标号，长老要求用油漆将这些石 柱重新粉刷一遍。 赫克托有 K 桶颜色各不相同的油漆， 第 i 桶油漆恰好可以粉刷 Ci 根石柱， 并且，C1+C2+C3…CK=N（即粉刷 N 根石柱正好用完所有的油漆） 。长老为了刁难赫克托，要 求相邻的石柱颜色不能相同。 喜欢思考的赫克托不仅没有立刻开始粉刷，反而开始琢磨一些奇怪的问题，比如，一共 有多少种粉刷的方案？ 为了让赫克托尽快开始粉刷，请你尽快告诉他答案
输入
第一行一个正整数 T，表示测试数据组数。对于每一组测试数据数据： 第 1 行：一个正整数 K。 第 2 行：K 个正整数，表示第 i 桶油漆可以粉刷的石柱个数 Ci。
输出
对于每组输入数据，输出一行一个整数，表示粉刷的方案数 mod 1000000007。
样例输入 复制
3
3
1 2 3
5
2 2 2 2 2
10
1 1 2 2 3 3 4 4 5 5样例输出 复制
10
39480
85937576提示
【数据说明】
30%的数据满足：N≤10, T≤5。
50%的数据满足：N≤15, T≤5。
80%的数据满足：K≤15,Ci≤5,T≤500。
100%的数据满足：K≤15,Ci≤16,T≤2000。