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

const int N = ((int)(5e3))+50;
const int mod = ((int)(1e9))+7;

long long dp[N+50];
int tab[N];
int n;

int main(){
	ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); cout.tie( 0 );
	cin>>n;
	for (int i = 0; i < n; i++){
		cin>>tab[i];
	}
	sort(tab, tab+n);
	dp[0] = 1;
	for (int i = 0; i < n; i++){
		dp[N] *= 2;
		if(dp[N] >= mod) dp[N] -= mod;
		for (int j = N-1; j >= tab[i]-1; j--){
			if(j+tab[i] >= N){
				dp[N] += dp[j];
				if(dp[N] >= mod) dp[N] -= mod; 
			} else {
				dp[j+tab[i]] += dp[j];
				if(dp[j+tab[i]] >= mod) dp[j+tab[i]] -= mod; 
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++){
		ans += dp[i];
		if(ans >= mod) ans -= mod; 
	}
	cout<<ans;
	return 0;
}