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

using namespace std;

long a[5001];
long b[26000000];
long nk[5001][5001];

long newton(long n, long k)
{
	if (nk[n][k] == 0)
		nk[n][k] = (k == n || k == 0) ? 1 : (newton(n - 1, k - 1) + newton(n - 1, k)) % 1000000007;
	return nk[n][k];
}

int main()
{
	//printf(" %ld", 5000);
	//for (long i = 1; i < 5001; i++)
	//	printf(" %ld", i);
	//return 0;

	for (long n = 0; n < 5001; n++) 
	{
		nk[n][0] = nk[n][n] = 1;
		for (long k = 1; k < n; k++)
			nk[n][k] = (nk[n - 1][k - 1] + nk[n - 1][k]) % 1000000007;
	}
	long n, ai;
	scanf("%ld", &n);
	//n = 5000;
	for (long i = 0; i < n; i++)
	{
		scanf("%ld", &ai);
		a[ai]++;
		//a[i + 1]++;
	}
	long res = 0, p = 1000000007, s = 0, bk;
	long long r, l;
	b[0] = 1;
	for (long i = 1; i <= 5000; i++)
	{
		if (a[i] == 0 && s < i)
			break;
		if (a[i] > 0)
		for (long k = min(s, 5000l); k >= i - 1; k--)
		{
			if (b[k] > 0)
			{
				bk = b[k];
				for (long j = 1; j <= a[i]; j++)
				{
					l = nk[a[i]][j];
					r = (l * bk) % p;
					b[min(k + i * j, 5000l)] = (r + b[min(k + i * j, 5000l)]) % p;
					res = (r + res) % p;
				}
			}
		}
		s += i * a[i];
	}
	printf("%ld", res);
	return 0;
}