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
#include <iostream>
#include <algorithm>
using namespace std;
int tab[25000000];
int wejscie[5000];
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
int n;
long long int suma=0, x=0;
cin>>n;
for(int i=0; i<n; i++) {
    cin>>wejscie[i];
}
sort(wejscie, wejscie+n);
tab[0]=1;
for(int i=0; i<n; i++) {
        x=(x*2)%1000000007;
    for(int j=4998; j>=wejscie[i]-1; j--) {
            if(j+wejscie[i]<4999) {
        tab[j+wejscie[i]]=(tab[j+wejscie[i]]+tab[j])%1000000007;
            }
            else {
                x+=tab[j];
            }
    }
}
for(int i=1; i<=4998; i++) {
    suma+=tab[i];
}
cout<<(suma+x)%1000000007;
}