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

using namespace std;

constexpr int P = 1000000007;
constexpr int MAXN = 5000;
constexpr int MAXA = 5000;

int a[MAXN];
int s[MAXA + 1];
int n;

void Add(int &x, int y)
{
	x += y;
	if (x >= P) x -= P;
}

void Process(int x)
{
	for (int i = MAXA; i >= x - 1; i--)
		Add(s[min(MAXA, i + x)], s[i]);
}

int Solve()
{
	s[0] = 1;
	for (int i = 1; i <= MAXA; i++)
		s[i] = 0;
	for (int i = 0; i < n; i++)
		Process(a[i]);
	int res = 0;
	for (int i = 1; i <= MAXA; i++)
		Add(res, s[i]);
	return res;
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	printf("%d\n", Solve());
	return 0;
}