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
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 5000 + 7;
const long long MOD = 1e9 + 7;

int n;
long long A[N];

long long S = 0;
long long Dp[N*N];

void init() {
    cin >> n;

    for (int i=1; i<=n; i++) {
        cin >> A[i];
        
        S += A[i];
    }  
    
    sort(A+1, A+n+1);
}
        
void solve() {
     for (int i=1; i<=n; i++) {
         for (int j=S; j>A[i]; j--) {
             if (A[i] <= j - A[i] + 1) {
                 Dp[j] = (Dp[j] + Dp[j-A[i]]) % MOD; 
             }
         }
        
         if (A[i] == 1) {
             Dp[A[i]] = (Dp[A[i]] + 1) % MOD;
         }
     }
      
     long long sum = 0;
    
     for (int i=1; i<=S; i++) {
         sum = (sum + Dp[i]) % MOD;
     }
     
     cout << sum << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    solve();

    return 0;
}