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

#define MOD 1000000007

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::vector<int> V(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> V[i];
        sum += V[i];
    }
    sort(V.begin(), V.end());

    std::set<int, std::greater<int>> S;
    std::vector<unsigned int> D(V.back() + 2);
    std::vector<bool> B(V.back() + 2);
    D[0] = 1;
    B[0] = 1;
    S.insert(0);
    for (int j = 0; j < V.size(); ++j) {
        int k = V[j];
        for (auto i : S) {
            if (i >= k - 1) {
                int x = i + V[j];
                if (x > V.back()) x = V.back() + 1;
                D[x] = (D[x] + D[i]) % MOD;
                if (!B[x]) {
                    S.insert(x);
                    B[x] = 1;
                }
            } else break;
        }
    }

    long long ret = 0;
    for (auto i : S) {
        if (i != 0) ret = (ret + D[i]) % MOD;
    }

    std::cout << ret;

    return 0;
}