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
#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;
long long n, paczka[5007], nowe[5007], sumy[5007], ponad, wynik;

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> paczka[i];
    }

    sort(paczka, paczka+n);

    sumy[0]=1;
    for(int i=0; i<n; i++)
    {
        int x = paczka[i];
        ponad*=2;
        ponad%=MOD;
        for(int j=x-1; j<=5000; j++)
        {
            if(j+x>5000)
            {
                ponad+=sumy[j];
                ponad%=MOD;
            }
            else
            {
                nowe[j+x]=sumy[j+x]+sumy[j];
                nowe[j+x]%=MOD;
            }
        }

        for(int j=1; j<=5000; j++)
            sumy[j]=nowe[j];
    }

    for(int i=1; i<=5000; i++)
    {
        wynik+=sumy[i];
        wynik%=MOD;
    }

    wynik+=ponad;
    wynik%=MOD;

    cout << wynik%MOD << endl;
}