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
// Karol Kosinski 2020
#include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOD(i,b,a) for(int i=(b)-1;i>=(a);--i)
using namespace std;

const int NX = 5003;
const int MOD = 1'000'000'007;

int A[NX];
int Sums[NX][NX];

int main()
{
    int n, sum = 0, res = 0;
    scanf("%d", &n);
    FOR(i,0,n) scanf("%d", A + i);
    sort(A, A + n);
    Sums[0][0] = 1;
    FOR(i,0,n)
    {
        FOR(s, 0, sum + 1) Sums[ i + 1 ][s] = Sums[i][s];
        FOD(s, sum + 1, A[i] - 1)
        {
            int next = min(NX - 1, s + A[i]);
            Sums[ i + 1 ][next] += Sums[i][s];
            Sums[ i + 1 ][next] %= MOD;
        }
        sum += A[i];
        sum = min(NX - 1, sum);
    }
    FOR(s,0,sum) res = (res + Sums[n][ s + 1 ]) % MOD;
    printf("%d\n", res);
    return 0;
}