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
#include <bits/stdc++.h>
const int N=5010;
const int A=5010;
const long long M=1000000007;

using namespace std;

int n,m,a[N];
long long d[N],s[A+1],h,w;

int main() {
	scanf("%d",&n);
	for (int i=0; i<n; i++) {
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	s[0]=1;
	for (int i=0; i<n; i++) {
		h=0;
		for (int j=A; j>=a[i]-1; j--) {
			h+=s[j];
			h%=M;
		}

		d[i]=d[max(0,i-1)]+h;
		d[i]%=M;

		s[A]*=2; s[A]%=M;
		for (int j=A-1; j>=a[i]-1; j--) {
			s[min(j+a[i],A)]+=s[j];
			s[min(j+a[i],A)]%=M;
		}
	}
	printf("%lld\n",d[n-1]);
	return 0;
}