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
#include <bits/stdc++.h>
 
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
typedef pair<int,int> PI; 
typedef pair<LL,LL> PLL;
typedef unsigned long long ULL;
typedef pair<double,double> PD;
 
#define FOR(x, b, e) for(int x = b; x<= (e); x++)
#define FORD(x, b, e) for(int x = b; x>= (e); x--)
#define REP(x, n) for(int x = 0; x<(n); ++x)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
 
#define PB push_back
#define IN insert
#define ST first
#define ND second
#define INF 2000000011
#define MOD 1000000007

#define MAXS 5010

int n;
LL zlicz[MAXS];
int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    VI arr(n);
    REP(i,n)
        cin>>arr[i];
    sort(ALL(arr));
    
    zlicz[0]=1;
    LL poza=0;
    REP(i,n){
        poza=(poza*2LL)%MOD;
        FORD(j,5000,arr[i]-1){
            if(arr[i]+j>5000)
                poza=(poza+zlicz[j])%MOD;
            else
                zlicz[j+arr[i]]=(zlicz[j+arr[i]]+zlicz[j])%MOD;
        }
    }

    LL wyn=poza;
    FOR(i,1,5000)
        wyn=(wyn+zlicz[i])%MOD;
    cout<<wyn<<"\n";


}