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
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <iterator>

using namespace std;

const int NMAX = 5000 + 7;
const int rest = 1000 * 1000 * 1000 + 7;
long long result_low = 0;
long long result_hight = 0;


int n;
int a[NMAX];

struct val {
	long long int val = 0;
};

map<int, val> check;

int main() {
	(void)! scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		(void)! scanf("%d", &a[i]);
	}

	sort(a, a + n);

	int hight_range = a[n - 1] + 2;
	//check.insert(0);
	check[0].val = 1;

	for(int i = 0; i < n; i++) {
		int x = a[i];
		auto it = check.rbegin();

		/*if(x == 1) {
			check[x]++;
			continue;
		}*/

		//if(x < hight_range)
		result_hight = (result_hight * 2) % rest;

		for(auto it = check.rbegin(); it != check.rend(); ++it) {
	//		printf("x: %d *it = %d\n", x, *it);
			if(x <= it->first + 1) {
				int w = it->first + x;
				// ++it;
				if(hight_range < w)
					result_hight = (result_hight + it->second.val) % rest;
				else
					check[w].val = (check[w].val + it->second.val) % rest;
			} else {
				break;
			}
		}

		for(auto it = check.begin(); it != check.end();) {
			if(x <= it->first + 1)
				break;

			result_low = (result_low + it->second.val) % rest;
			it = check.erase(it);
		}
	}

	for(auto it = check.begin(); it != check.end();) {
		result_low = (result_low + it->second.val) % rest;
		it = check.erase(it);
	}


	/*for(auto it = check.begin(); it != check.end(); ++it) {
		printf(".. %d %lld \n", it->first, it->second.val);
	}*/



	//printf("%lu\n", check.size());
	//printf("%lld\n", result_hight);
	printf("%lld\n", (result_low + result_hight + rest - 1) % rest);
	return 0;
}