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

using namespace std;

typedef pair<int,int> II;

#define INFTY 2000000000
#define MOD 1000000007

int main()
{
    std::ios::sync_with_stdio(0);

    int i, j, n;

    cin >> n;
    
    vector<int> c(n);

    for (i=0; i<n; i++)
      cin >> c[i];
          
    sort(c.begin(), c.end());
    
    vector<int> t(5001,0);
    
    t[0] = 1; // zb. pusty
    
    for (i=0; i<n; i++)
    { 
      int x = c[i];
      for (int s = 5000; s>=x-1; s--)
      {
        int sx = min(5000, s+x);
        t[sx] = (t[sx] + t[s]) % MOD;
      }   
    }
    
    int res = 0;
    
    for (auto &e : t)
      res = (res + e) % MOD;
   
    cout << res - 1 << "\n";

    return 0;
}