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

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll>  vll;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


const ll mod = 1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;

    vll t = {0};

    ll x;
    for(int i = 0; i < n; i++){
        cin >> x;
        t.push_back(x);
    }

    sort(t.begin(), t.end());

    vll d(5003,0);
    vector<vll> dp(n+1,d);

    dp[0][0]=1;

    if(t[1]!=1){
        cout << "0\n";
        return 0;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 5003; j++)
            dp[i][j]=dp[i-1][j];
        for(int j = t[i]-1; j < 5003; j++)
            dp[i][min(5002ll, j+t[i])]=(dp[i-1][j]+dp[i][min(5002ll, j+t[i])])%mod;
    }
    ll sum = 0;
    for(int i = 1; i < d.size(); i++){
        sum = (sum+dp[n][i])%mod;
    }

    // for(int i = 0; i <= n; i++){
    //     for(int s = 0; s < 30; s++)
    //         cout << dp[i][s] << " ";
    //     cout << "\n";
    // }

    cout << sum << "\n";
}