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
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> boxes;


    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        int next_box;
        cin >> next_box;
        sum += next_box;
        boxes.push_back(next_box);
    }

    sort(boxes.begin(), boxes.end());
    auto* array = new long long[sum + 1];
    for(long long i = 0; i < sum + 1; i++)
        array[0] = 0;

    array[0] = 1;
    long long max_value = 0;

    for(int i = 0; i < boxes.size(); i++)
    {
        if(max_value < boxes[i] - 1)

            break;
        for(long long j = max_value; j >= boxes[i] - 1; j--)

        {
            max_value = max(max_value, j + boxes[i]);
            array[j + boxes[i]] += array[j];
            array[j + boxes[i]] %= 1000000007;



        }
    }
    long long result = 0;
    for(long long i = 1; i <= max_value; i++)

//        cout<<i<<": "<<array[i]<<endl;
    {
        result += array[i];
        result %= 1000000007;
    }
    cout<<result<<endl;

    delete [] array;

    return 0;
}