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
#include<bits/stdc++.h>
using namespace std;
template <typename T> T getczary(){//magia!
  int ujemna = false, znak = getchar_unlocked();
  T wynik = (T)0;
  while(!isdigit(znak)){
    if(znak == '-')
      ujemna = true;
    znak = getchar_unlocked();
  }
  while(isdigit(znak)){
    wynik *= 10;
    wynik += znak - '0';
    znak = getchar_unlocked();
  }
  if(ujemna)
    wynik *= -1;
  return wynik;
}
#define pc(x) putchar_unlocked(x);
inline void kout(int n){
  int N = n, rev, count = 0;
  rev = N;
  if (N == 0) { pc('0'); pc('\n'); return ;}
  while ((rev % 10) == 0) { count++; rev /= 10;}
  rev = 0;
  while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
  while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
  while (count--) pc('0');
}
int sum[25000007];
int main(){
  int k, mod = 1000000007, res = 0, maksSum = 1;
  k = getczary<int>();
  vector<int> v(k);
  for(int i = 0;i < k;i++){
    v[i] = getczary<int>();
  }
  sort(v.begin(), v.end());
  sum[0] = 1;
  for(int i = 0;i < k;i++){
    for(int x = maksSum;x >= v[i] - 1;x--){
      sum[x + v[i]] = (sum[x + v[i]] + sum[x]) % mod;
if(sum[x+v[i]] >0) maksSum = max(maksSum, x + v[i]);
}
}
  for(int i = 1;i <= maksSum;i++)
    res = (res + sum[i]) % mod;
  kout(res);
}