Description
有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。
所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两
个相邻木块颜色不同的着色方案。
Input
第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。
Output
输出一个整数，即方案总数模1,000,000,007的结果。
Sample Input
3
1 2 3
1 2 3
Sample Output
10
HINT
100%的数据满足：1 <= k <= 15, 1 <= ci <= 5
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~记忆化搜索~
剩余数目相同的颜色之间没有本质区别，所以我们只要记录每种剩余颜色数目对应的颜色种类数就可以了。
用f[x][y][z][v][k][w]表示剩余1，2，3，4，5个的颜色分别有x，y，z，v，k，w种，前一个位置填还有w数目的颜色的种类数，那么直接记忆化搜索就可以了。
注意：
1.判断的时候要判断是否还有xyzvk是否为0；
2.x-(w==2)而不是x=(w==1)，因为前一个颜色填入的时候还没有减去1；
3.开long long!
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
#define modd 1000000007int n,a[6];
ll f[16][16][16][16][16][6];
bool b[16][16][16][16][16][6];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}ll dfs(int x,int y,int z,int v,int k,int w)
{if(b[x][y][z][v][k][w]) return f[x][y][z][v][k][w];if(!(x+y+z+v+k)) return 1;ll tot=0;if(x) (tot+=(x-(w==2))*dfs(x-1,y,z,v,k,1))%=modd;if(y) (tot+=(y-(w==3))*dfs(x+1,y-1,z,v,k,2))%=modd;if(z) (tot+=(z-(w==4))*dfs(x,y+1,z-1,v,k,3))%=modd;if(v) (tot+=(v-(w==5))*dfs(x,y,z+1,v-1,k,4))%=modd;if(k) (tot+=k*dfs(x,y,z,v+1,k-1,5))%=modd;b[x][y][z][v][k][w]=1;return f[x][y][z][v][k][w]=tot;
}int main()
{n=read();for(int i=1;i<=n;i++) a[read()]++;printf("%lld\n",dfs(a[1],a[2],a[3],a[4],a[5],0));return 0;
}