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
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

const int p = 1000000000 + 7;
inline void add(int &x, int y) { x += y; if (x >= p) x -= p; }
inline void sub(int &x, int y) { x -= y; if (x < 0) x += p; }
inline int myMin(int a, int b) { return a < b ? a : b; }

const int N = 5000 + 9;

int a[N];
int cnt[N][N];

int main() {
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; ++i) scanf("%d", a + i);
	sort(a, a + n);

	cnt[0][0] = 1;

	for (int i=0; i<n; ++i) for (int s=0; s<a[n-1]; ++s) {
		// skip a[i]
		add(cnt[i+1][s], cnt[i][s]);

		// include a[i]
		if (s + 1 >= a[i])
			add(cnt[i+1][myMin(s + a[i], a[n-1] - 1)], cnt[i][s]);
	}

	int res = 0;
	for (int s=0; s<a[n-1]; ++s) add(res, cnt[n][s]);

	sub(res, 1);
	printf("%d\n", res);
	return 0;
}