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
77
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define MAX_N	5010
#define MAX_A	5010
#define P	1000000007

int N, R;
vector<int> A;

map<int, int> s;
int sm;

void np(int ai) {
	for (auto it = s.begin(); it != s.end() && it->first < ai - 1; it = s.begin()) {
		R = (R + it->second) % P;
		s.erase(it);
	}

	map<int, int> t;

	for (auto it = s.begin(); it != s.end(); ++it) {
		t.insert(t.end(), pair<int, int>(it->first + ai, it->second));
	}

	auto it1 = s.begin();
	auto it2 = t.begin();
	while (it1 != s.end() && it2 != t.end()) {
		if (it2->first == it1->first) {
			it1->second = (it1->second + it2->second) % P;
			it1++;
			it2++;
		} else if (it2->first < it1->second) {
			s.insert(it1, pair<int, int>(it2->first, it2->second));
			it2++;
		} else {
			it1++;
		}
	}
	while (it2 != t.end()) {
		s.insert(s.end(), pair<int, int>(it2->first, it2->second));
		it2++;
	}

	sm += ai;
}

int main() {
	int ai;

	scanf("%d", &N);

	A.reserve(N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &ai);
		A.push_back(ai);
	}
	sort(A.begin(), A.end());

	sm = 1;
	s[0] = 1;
	for (int i = 0; i < N && A[i] <= sm; ++i) {
		np(A[i]);
	}

	for (auto it = s.begin(); it != s.end(); ++it) {
		R = (R + it->second) % P;
	}

	printf("%d\n", R - 1);

	return 0;
}