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
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc seconds
using ll=long long;
using pii=pair<int,int>;
const int R=5000,mod=1e9+7;
ll dp[R+6];
int sum[R+6];
vector<int>tab;
ll il[R+6],dod[R+6];
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;cin>>a;
        tab.push_back(a);
    }
    sort(tab.begin(),tab.end());
    if(tab[0]!=1)
    {
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        int a=tab[i-1];
        if(sum[i-1]<a-1)
        {
            dp[n]=dp[i-1];
            break;
        }

        sum[i]=sum[i-1]+a;
        ll add=0;
        ll d500=0;
        for(int j=a-1;j<=R;j++)
        {
            if(j<min(R,a-1+a)){il[j]+=dod[j];dod[j]=0;}
            il[j]%=mod;
            add+=il[j];
            int id=j+a;
            if(id>=R)
            {
                d500+=il[j];
                d500%=mod;
                continue;
            }
            il[id]+=dod[id];
            dod[id]=il[j];
            il[id]%=mod;
            add%=mod;
        }
        il[R]+=d500;
        il[R]%=mod;

        if(a==1){add++;il[1]++;}
        dp[i]=(dp[i-1]+add)%mod;
    }
    cout<<dp[n];
}