有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

　　第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。

　　输出一个整数，即方案总数模1,000,000,007的结果。

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define rhl (1000000007)15 #define inf (1<<30)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 //f[a1][a2][a3][a4][a5][last]表示剩余次数为ai的颜色有多少种,上一次是用的次数为last的颜色24 ll f[17][17][17][17][17][6];25 int num[6],k,x;26 27 il int gi(){28     RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();29     if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x;30 }31 32 il ll dfs(RG int a1,RG int a2,RG int a3,RG int a4,RG int a5,RG int last){33     if (f[a1][a2][a3][a4][a5][last]) return f[a1][a2][a3][a4][a5][last];34     if (!(a1|a2|a3|a4|a5)) return f[a1][a2][a3][a4][a5][last]=1; RG ll now=0;35     if (a1) now+=(a1-(last==2))*dfs(a1-1,a2,a3,a4,a5,1)%rhl;36     if (a2) now+=(a2-(last==3))*dfs(a1+1,a2-1,a3,a4,a5,2)%rhl;37     if (a3) now+=(a3-(last==4))*dfs(a1,a2+1,a3-1,a4,a5,3)%rhl;38     if (a4) now+=(a4-(last==5))*dfs(a1,a2,a3+1,a4-1,a5,4)%rhl;39     if (a5) now+=a5*dfs(a1,a2,a3,a4+1,a5-1,5)%rhl;40     return f[a1][a2][a3][a4][a5][last]=now%rhl;41 }42 43 il void work(){44     k=gi(); for (RG int i=1;i<=k;++i) x=gi(),num[x]++;45     printf("%lld",dfs(num[1],num[2],num[3],num[4],num[5],0)); return;46 }47 48 int main(){49     File("color");50     work();51     return 0;52 }