有n个木块，从左到右排成一排，你有k种颜色，每种颜色的可以涂ci个木块，所有的颜色正好够涂所有的木块，即c1+c2+...+ck=n。涂色时要求任意两块相邻木块不能同色，请统计出不同着色方案的总数。两种着色方案是不同的当且仅当两种方案至少有一个位置的木块颜色是不同的。
第一行输入一个T，表示数据组数，每组数据的第一行一个正整数k(1<=k<=30)表示颜色种数，第二行k个整数c1,c2,...,ck(1<=ci<=30)，表示每种颜色可涂的木块数。
输出T行，表示每一组的方案数模1,000,000,007的结果。