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

using namespace std;

#define D(x)

#define MAX 5010
#define P 1000000007LL

typedef long long I;

I v[MAX], res;
int a[MAX];

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    sort(&a[0],&a[n]);
    v[0] = 1;
    for(int i=0;i<n;i++) {
        for(int j=MAX-1;j>=a[i]-1;j--) {
            int nv = j+a[i];
            if(nv>=MAX) nv = MAX-1;
            v[nv] = (v[nv] + v[j]) % P;
        }
        D(
        for(int i=0;i<13;i++) cout << v[i] << " ";
        cout << "\n");
    }
    for(int i=1;i<MAX;i++) res=(res+v[i]) % P;
    cout << res << "\n";
}