神奇的Dp

/**************************************************************
    Problem: 1079
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:612 ms
    Memory:50444 kb
****************************************************************/
 
/*
    计算出 f j 表示j个位置 
    不限制每种颜色的数量 的方案数
    然后 2^15 深搜 
    如果 k 被限制 则 不符合的方案数就是 f j-(c[k]+1) 
    利用容斥 奇减偶加  
    错解。。。因为位置对答案有影响
    f a,b,c,d,e,last 表示 还能涂一下的有a个 两下的有b个  5下的有e个 
    上一次用的是能涂last下的颜色中的一种颜色
    因为上一次的last 这一次变味了last-1 所以如果我们选择last-1这种颜色 
    就只有last-1-1种选择方法 （相邻不能一样 
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P=1000000007;
int n,m,col[6];
ll f[16][16][16][16][16][6];
ll dfs(int a,int b,int c,int d,int e,int last)
{
    if(f[a][b][c][d][e][last]!=-1) return f[a][b][c][d][e][last];
    if(a+b+c+d+e==0) return 1; // 用完了 一种情况 
    ll res=0;
    if(a) res=res+(a-(last-1==1))*dfs(a-1,b,c,d,e,1)%P;
    if(b) res=res+(b-(last-1==2))*dfs(a+1,b-1,c,d,e,2)%P;
    if(c) res=res+(c-(last-1==3))*dfs(a,b+1,c-1,d,e,3)%P;
    if(d) res=res+(d-(last-1==4))*dfs(a,b,c+1,d-1,e,4)%P;
    if(e) res=res+e*dfs(a,b,c,d+1,e-1,5)%P;
    // 用了i i-1的个数就要增加 
    f[a][b][c][d][e][last]=res;
    return res;
     
}
int main()
{
    memset(f,-1,sizeof(f));
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++) scanf("%d",&x),col[x]++;
    printf("%lld\n",dfs(col[1],col[2],col[3],col[4],col[5],0)%P);
    return 0;
}