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
#include <bits/stdc++.h>

using namespace std;

const long long int p=1e9+7;

long long inline mod(const long long& x){return x>=p?x-p:x;}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int>t;
    long long dp[5005][2]={};
    int n;
    long long a;
    bool first;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        t.push_back(a);
    }
    sort(t.begin(),t.end());
    if(t[0]!=1)cout << "0" << endl;
    else{
        dp[1][0]=1;
        for(a=1;a<n;a++){
            if(t[a]==1){
                dp[1][a&1]=dp[1][1-(a&1)]+1;
                for(int j=1;j<=a;j++)dp[j+1][a&1]=mod(dp[j][1-(a&1)]+dp[j+1][1-(a&1)]);
            }
            else break;
        }
        for(int i=a;i<n;i++){
            first=true;
            for(int j=1;j<min(2*t[i]-1,5001);j++)dp[j][i&1]=dp[j][1-(i&1)];
            for(int j=max(t[i]-1,1);j<=5000;j++){
                    if(t[i]+j<=5000)dp[t[i]+j][i&1]=mod(dp[j][1-(i&1)]+dp[t[i]+j][1-(i&1)]);
                    else{
                        if(first){
                            dp[0][i&1]=mod(dp[j][1-(i&1)]+mod(2*dp[0][1-(i&1)]));
                            first=false;
                        }
                        else dp[0][i&1]=mod(dp[0][i&1]+dp[j][1-(i&1)]);
                    }
            }
        }
        a=0;
        for(int i=0;i<=5000;i++)a=mod(a+dp[i][1-(n&1)]);
        cout << a << endl;
    }
}