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 <bits/stdc++.h>
#define IOSTREAM_BOOST true
#define MOD int(1e9 + 7)
using namespace std;

int n;
vector<int> t;
int dp[5005];
int excess = 0;

void add(int index, int val){
    if(index <= 5000) dp[index] = (dp[index] + val) % MOD;
    else excess = (excess + val) % MOD;
}

int main()
{
    #if IOSTREAM_BOOST
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif
    
    cin >> n;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        t.push_back(a);
    }
    sort(t.begin(), t.end());
    dp[0] = 1;

    for(int x : t){
        excess = (2 * excess) % MOD;
        for(int i = 5000; i >= x - 1; i--) add(i + x, dp[i]);
    }
    long long w = 0;
    for(int i = 1; i <= 5000; i++) w += dp[i];
    w += excess;
    cout << (w % MOD) << "\n";
    return 0;
}