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 <iostream>
#include <algorithm>
#include <vector>

#define PRIME 1000000007
#define SIZE 5000

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;

    long long sums[SIZE + 1] = {0};
    std::cin >> n;
    std::vector<int> sizes;
    sizes.resize(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> sizes[i];
    }
    std::sort(sizes.begin(), sizes.end());
    sums[0] = 1;
    for (auto s: sizes) {
        sums[SIZE] *= 2;
        sums[SIZE] %= PRIME;
        for (int pos = SIZE - 1; pos >= s - 1; --pos) {
            auto newPos = std::min(SIZE, pos + s);
            sums[newPos] += sums[pos];
            sums[newPos] %= PRIME;
        }
    }
    long long total = 0;
    for (int i = 1; i <= SIZE; ++i) {
        total += sums[i];
        total %= PRIME;
    }
    std::cout << total << std::endl;
    return 0;
}