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<cstdio>
#include<algorithm>

int n;
int a[5003];
int dp[5003*5003];
int res, max_res, new_ind;

const int MOD = 1000000007;

using namespace std;

int main() {
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
	scanf("%d", &a[i]);
  }
  sort(a, a+n);
  
  if (a[0] != 1) {
	printf("0\n");
	return 0;
  }
  dp[0] = 1;
  dp[1] = 1;
  max_res = 1;
  
  for (int i = 1; i < n; i++) {
	for (int j = max_res; j >= a[i] - 1; j--) {
		new_ind = min(j+a[i], 5000);
		dp[new_ind]+=dp[j];
		if(dp[new_ind] > 0) {
			max_res = std::max(max_res, new_ind);
		}
		dp[new_ind] %= MOD;
	}		
  }
  for (int i = 1; i <= max_res; i++) {
	res += dp[i];
	res %= MOD;
  }
  
  printf("%d\n", res);
  
  return 0;
}