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
#include <cstdio>
#include <cstdlib>

#include <algorithm>

const unsigned int MAX_SWEETS_IN_BAG = 5000;
const unsigned int MODULUS = 1000 * 1000 * 1000 + 7;

unsigned int sweets[5000] = { 0 };
unsigned int sweet_counts[MAX_SWEETS_IN_BAG] = { 0 };
unsigned int sweets_above_limits = 0;

int main() {
    unsigned int n;
    scanf("%u", &n);

    sweet_counts[0] = 1;

    for (unsigned int i = 0; i < n; i++) {
        scanf("%u", &sweets[i]);
    }

    std::sort(sweets, sweets + n);

    for (int i = 0; i < n; i++) {
        const int s = (int)sweets[i];
        sweets_above_limits = (2 * sweets_above_limits) % MODULUS;
        for (int j = MAX_SWEETS_IN_BAG - 1; j >= s - 1; j--) {
            if (j + s < MAX_SWEETS_IN_BAG) {
                sweet_counts[j + s] = (sweet_counts[j + s] + sweet_counts[j]) % MODULUS;
            } else {
                sweets_above_limits = (sweets_above_limits + sweet_counts[j]) % MODULUS;
            }
        }
    }

    unsigned int total = 0;
    for (int i = 0; i < MAX_SWEETS_IN_BAG; i++) {
        total = (total + sweet_counts[i]) % MODULUS;
    }
    total = (total + sweets_above_limits) % MODULUS;

    // Remove the empty set
    total = (total + MODULUS - 1) % MODULUS;
    printf("%u\n", total);

    return 0;
}