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
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>

#define DEBUG0(x) x
#ifdef HOME__
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)

#define BASE 1000000007LL
#define MOD(n) (((long long)n)%BASE)

using namespace std;

const int MAX_N = 5001;

int n;
map<int, int> solutions;
int input[MAX_N];

long long over5000 = 0LL;

bool process(int input) {
	DEBUG(cerr<<"Processing "<<input<<endl;)
//	if (solutions.empty() && input == 1) {
//		solutions[1] = 1;
//		return true;
//	}
	auto end = solutions.lower_bound(input-1);
	if (end == solutions.end()) {
		DEBUG(cerr << "cannot match " << input << endl;)
		return false;
	}
	DEBUG(int affected = 0;)
	over5000 = MOD(over5000*2);
	for(auto iter = solutions.end(); iter-- != end;) {
		DEBUG(cerr << "can join with " << iter->first << " - " << iter->second << " times"<<endl; ++affected;)
		if (iter->first + input > 5000)
			over5000 = MOD(over5000 + iter->second);
		else
			solutions[iter->first + input] = MOD(solutions[iter->first + input] + iter->second);
	}
	DEBUG(cerr << "affected " << affected << endl;)
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	REP(x,n)
		cin>>input[x];
	sort(input, input+n);
	solutions[0] = 1;
	REP(x,n)
		if (!process(input[x]))
			break;
	long long sum = -1;
	FOREACH(it, solutions)
		sum = MOD(sum+it->second);
	cout<<MOD(sum+over5000);
	return 0;
}