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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define st first
#define nd second
#define pb push_back

const int maxn = 5e3;
const int M = 1e9 + 7;
int a[maxn + 5];
ll dp[maxn + 5];
ll D[maxn + 5];
void mltp(ll &x, ll y){
	x *= y;
	if(x >= M)
		x %= M;
}
void add(int pos, ll val){
	for(int i = pos; i <= 5001; i += i & (-i)){
		D[i] += val;
		if(D[i] >= M)
			D[i] %= M;
	}
}
ll sum(int poc, int kon){
	ll ret = 0;
	for(int i = kon; i >= 1; i -= i & (-i)){
		ret += D[i];
		ret %= M;
	}
	for(int i = poc - 1; i >= 1; i -= i & (-i)){
		ret -= D[i];
		ret = (ret + M) % M;
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	dp[0] = 1;
	for(int i = 1; i <= n; i++){ /// dp5001 to dla s > 5000
		add(5001,dp[5001]);
		mltp(dp[5001],2);
		int poc = max(a[i] - 1,5001 - a[i]);
		int kon = 5000;
		ll s = sum(poc,kon);
		dp[5001] += s;
		if(dp[5001] >= M)
			dp[5001] %= M;
		add(5001,s);
		for(int j = 5000; j >= 1; j--){
			int p = j - a[i];
			if(a[i] - 1 > p)
				continue;
			if(p < 0 || p >= j)
				continue;
			add(j,dp[p]);
			dp[j] += dp[p];
			if(dp[j] >= M)
				dp[j] %= M;
		}
	}
	//~ for(int i = 30; i >= 1; i--)
		//~ cout << "dp["<<i<<"]: " << dp[i] << '\n';
	cout << sum(1,5001) << '\n';
	return 0;
}