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
#include <bits/stdc++.h>
using namespace std;
long long C=1000*1000*1000+7;
int main(){
ios_base::sync_with_stdio(0);
int n;
cin >> n;
int t[n];
int maks=1;
map<int,int> m;
for (int i=0; i<n;i++){
    cin >> t[i];
    maks+=t[i];
}
long long wyn[maks];
for (int i=0; i<maks;i++){
    wyn[i]=0;
}
sort(t,t+n);
wyn[0]=1;
int s=0;
for (int i=0; i<n;i++){
    int s2=s;
    s+=t[i];
    int l=s;
    //cout << s<<"<->"<<t[i]<<endl;
    while(s2>=t[i]-1){
        //cout << s2<<endl;
        wyn[s2+t[i]]+=wyn[s2];
        wyn[s2+t[i]]%=C;
        s2--;

    }
    /*for (int i=0; i<maks;i++){
        cout << wyn[i]<<" ";
    }
    cout << endl;*/
}
long long wynik=0;
for (int i=1; i<maks;i++){
    //cout << wyn[i]<<" ";
    wynik+=wyn[i];
    wynik%=C;
}
//cout << endl;
cout << wynik<<endl;
}