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
#include <bits/stdc++.h>
using namespace std;

//vector <long long> v;

//stack <long long> s, s2;
//bbbbaaaa
queue <long long> s;

long long int  z[1], x[6000], y[10000], m, szu, wy[10][1];
char s1[1], s2[1], cc;

int war(const void*a, const void *b)
{
    if(*(long long*)a>*(long long*)b)return(1);
    return(0);
}

int main()
{
    long long int c, d, e, f, g, i, j, q, t, k, a, n, b, w, p;

    t=1;
    //scanf("%lld", &t);
    //for(q=1; q<=t; q++)
    {
        scanf("%lld", &n);

        for(i=0; i<n; i++)
        {
            scanf("%lld", &y[i]);
        }

        sort(y, y+n);

        w=0;
        x[0]=1;

        for(j=0; j<n; j++)
        {
            a=y[j];
            for(i=5000+a; i>=2*a-1; i--)
            {
                b=x[i-a];
                x[min(5000+i-i, i)]+=b;
                x[min(5000+i-i, i)]%=1000000007;
                w+=b;
                w%=1000000007;
            }
        }


        printf("%lld\n", w);
    }

    return(0);
}