//#pragma comment(linker, "/STACK:167772160")

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <utility>

 #include <algorithm>

 #include <vector>

 #include <map>

 // #include<malloc.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define LL long long

 void fre() { freopen("in.txt","r",stdin);}

 const int inf = 0x3f3f3f3f;

 const double eps = 1e-;

 // const double pi = acos(-1);

 const LL mod = 1e9+;

 inline int r(){

     int x=,f=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int A[];

 LL dp[][][][][][];

 bool vis[][][][][][];

 LL work(int a,int b,int c,int d,int e,int last){

     LL tem;

     tem=;

     if((a|b|c|d|e)==) return ;

     if(vis[a][b][c][d][e][last]) return dp[a][b][c][d][e][last];

     if(a)

        tem+=(a-(last==))*work(a-,b,c,d,e,);

     if(b)

         tem+=(b-(last==))*work(a+,b-,c,d,e,);

     if(c)

         tem+=(c-(last==))*work(a,b+,c-,d,e,);

     if(d)

         tem+=(d-(last==))*work(a,b,c+,d-,e,);

     if(e)

         tem+=e*work(a,b,c,d+,e-,);

     dp[a][b][c][d][e][last]=(tem%mod);

     vis[a][b][c][d][e][last]=true;

     return dp[a][b][c][d][e][last];

 }

 int main(){

        // fre();

    int n;

    while(~scanf("%d",&n)){

       // clc(dp,0);

       // clc(vis,0);

       // clc(A,0);

       for(int i=;i<n;i++){

          int x;

          x=r();

          A[x]++;

       }

       LL ans;

       ans=work(A[],A[],A[],A[],A[],);

       cout<<ans<<endl;

    }

     return ;

 }