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
#include <bits/stdc++.h>
using namespace std;
#define MAXN 5007
#define P 1000000007ll
typedef long long ll;
ll tab[MAXN], sum, res;
int numbers[MAXN];
int n;
int main(){
  scanf("%d", &n);
  tab[0] = 1ll;
  for(int i = 0; i < n; i++){
    scanf("%d", &numbers[i]);
  }
  sort(numbers, numbers+n);
  int mymax = 5003;
  for(int i = 0; i < n; i++){
    for(int j = mymax + numbers[i]; j - numbers[i] >= numbers[i]-1; j--){
      tab[min(j, mymax)] += tab[j-numbers[i]];
      tab[min(j, mymax)] %= P;
    }
  }
  for(int i = 1; i <= mymax; i++){
    res += tab[i];
    res %= P;
  }
  printf("%lld\n", res);
}