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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> liczbs;
long long  wyniks[25000001];
const long long modulo = 1000000007;
long long maxwynik, totalwynik;

int main(){
    int b, n;
    wyniks[0] = 1;
    
    scanf("%d", &n);
    for(int i = 0; i<n; ++i){
        scanf("%d", &b);
        liczbs.push_back(b);
    }
    sort(liczbs.begin(), liczbs.end());
    for (int i = 0; i < n; ++i){
        // printf("%d %lld\n", liczbs[i], maxwynik);
        int l = liczbs[i];
        for(int j = maxwynik; j >= l-1; --j){            
            // printf("%d %d\n", l, j);
            totalwynik += wyniks[j];
            wyniks[j+l] += wyniks[j];
            if (wyniks[j] > 0 && j+l > maxwynik) {
                maxwynik = j+l;
            }
            wyniks[j+l] %= modulo;
            totalwynik %= modulo;
        }
        // printf("Po %d: %lld\n", liczbs[i], totalwynik);
    }

    printf("%lld\n", totalwynik);
    return 0;
}