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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define REP(i,n) for(int _n=(n), i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define TRACE(x) cerr << "TRACE(" #x ")" << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << endl;
typedef long long LL; typedef unsigned long long ULL;


#define BIGMOD 1000000007
#define MAX_N 10010

LL dp[MAX_N];

bool isValid(vector<int>& cukierki, int mask)
{
    int sum = 0;
    for (int i=0; i < cukierki.size(); i++)
    {
        if (!(mask & (1 << i))) continue;
        if (cukierki[i] > sum + 1) return false;
        sum += cukierki[i];
    }
    return true;
}

LL bruteSolve(vector<int> &cukierki)
{
    sort(cukierki.begin(), cukierki.end());
    LL res = 0;
    for (int mask=1; mask < (1 << cukierki.size()); mask++)
    {
        res += isValid(cukierki, mask) ? 1 : 0;
    }
    return res;
}

LL solve(vector<int> &cukierki)
{
    sort(cukierki.begin(), cukierki.end());
    for (int i=0; i < MAX_N; i++) dp[i] = 0;
    dp[0] = 1;
    const int maxN = MAX_N - 1;
    for (int v : cukierki)
    {
        for (int k=maxN; k >= v-1; --k)
        {
            LL ways = dp[k];
            if (ways==0) continue;
            //if (v > k + 1) continue; // => k < v - 1 

            int nv = min(maxN, k + v);
            dp[nv] += ways;
            if (dp[nv] > BIGMOD)
            {
                dp[nv] %= BIGMOD;
            }
        }
    }
    LL res = 0;
    for (int i=1; i < MAX_N; i++)
    {
        //if (dp[i]) printf("%d: %lld\n", i, dp[i]);
        res += dp[i];
    }
    return res % BIGMOD;
}

int main() 
{
    int n;
    scanf("%d", &n);
    vector<int> cukierki;
    for (int i=0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        cukierki.emplace_back(x);
    }
    
    LL res = solve(cukierki);
    printf("%lld\n", res);
    return 0;
}