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
73
74
75
76
#include <bits/stdc++.h>

using namespace std;


typedef long long LL;


const int MAXN = 5000;
const int MOD = 1000000007;


LL pow(LL a, LL b, LL m) {
	LL c = 1;

	while (b > 0) {
		if (b % 2 == 1)
			c = (c * a) % m;

		b /= 2;
		a = (a * a) % m;
	}

	return c;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	int a[MAXN];
	LL s[MAXN + 1];
	s[0] = 1;

	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		s[i + 1] = pow(2, i + 1, MOD);
	}

	sort(a, a + n);

	LL q = 0;
	LL dp[MAXN + 1] = {};

	dp[0] = 1;

	for (int i = 0; i < n; ++i) {
		LL db[MAXN + 1] = {};

		for (int j = 0; j <= MAXN; ++j) {
			if (a[i] > j + 1) {
				q += dp[j] * s[n - i - 1];
				q %= MOD;
			}
			else if (j + a[i] <= MAXN) {
				db[j + a[i]] += dp[j];
				db[j + a[i]] %= MOD;
			}

			db[j] += dp[j];
			db[j] %= MOD;
		}

		for (int j = 0; j <= MAXN; ++j)
			dp[j] = db[j];
	}

	LL p = s[n] - 1;
	LL res = (p - q + MOD) % MOD;

	cout << res << endl;
}