1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;

int n;
long long p = 1000000007ll;
long long C[5001];
long long T[5001];
int D[5002][5002];
//long long S[5002][5002];
int M[5002][5002];
int V[5002][5002];
int vv=5000;
void tp() {
    D[0][0]=1;
    for(int i =1;i<=5000;i++)
        for(int j =0;j<=i;j++) {
            if(j==0)D[i][j]=1;
            else D[i][j]=D[i-1][j-1]+D[i-1][j];
            D[i][j]%=p;
        }
}

void solve() {
    tp();
    for(int k = 1; k<=C[1];k++) 
        M[1][k]=V[1][k]=D[C[1]][k];

    for(int i =2;i<=vv;i++) {
        for(int k = 1; k<=C[i];k++) {
            for(int j =(k+1)*i-1;j<=vv;j++) {
                if(j-i*k<0)break;
                M[i][j]+=((long long)D[C[i]][k]*(long long)V[i-1][j-i*k])%p;
                M[i][j]%=p;
            }
        }
        for(int j =1;j<=vv;j++) {
            V[i][j]=V[i-1][j]+M[i][j];
            V[i][j]%=p;
        }
    }
    for(int i =1;i<=vv;i++)
        for(int j =1;j<=vv;j++) {
            V[i][j]=V[i][j]+V[i][j-1];
             V[i][j]%=p;
        }
    
    D[0][0]=0;
    for(int i =2;i<=5000;i++){
        D[i][0]=0;
        for(int j =1;j<=5000;j++) {
            D[i][j]+=D[i][j-1];
            D[i][j]%=p;
        }
    }
    
    T[1]=D[C[1]][C[1]];
    for(int i =2;i<=vv;i++) {//poprawic
       // cout<<i<<": S[C[i]][C[i]]: "<<D[C[i]][C[i]]<<"\n";
       // if(C[i]>0){
            T[i]=(((long long)D[C[i]][C[i]]*(T[i-1]-(long long)V[i-1][i-2]))+p)%p;
            T[i]=T[i]+T[i-1];
            T[i]%=p;
        //}
    }

    long long wynik = 0;
 
        wynik = T[vv];

    cout<<wynik<<"\n";



    /*
    cout<<"PASCAL:\n";
    for(int i = 1;i<=7;i++) {
        cout<<i<<": ";
        for(int j = 0;j<=18;j++) {
            cout<<D[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"PASCAL2:\n";
    for(int i = 1;i<=7;i++) {
        cout<<i<<": ";
        for(int j = 0;j<=18;j++) {
            cout<<S[i][j]<<" ";
        }
        cout<<"\n";
    }

    cout<<"CUKIERKI:\n";
    for(int i = 1;i<=7;i++) {
        cout<<i<<": "<<C[i]<<"\n";
    }

    cout<<"M: \n";
    for(int i = 1;i<=7;i++) {
        cout<<i<<": ";
        for(int j = 1;j<=18;j++) {
            cout<<M[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"V: \n";
    for(int i = 1;i<=7;i++) {
        cout<<i<<": ";
        for(int j = 1;j<=18;j++) {
            cout<<V[i][j]<<" ";
        }
        cout<<"\n";
    }*/


}

int main() {
    int c;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    vv = 0;
    for(int i = 0;i<n;i++) {
        cin>>c;
        vv=max(c,vv);
        C[c]++;
    }
    solve();

    return 0;
}