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
#define _CRT_SECURE_NO_WARNINGS 1
#define _WINSOCK_DEPRECATED_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

const int maxy = 5000;
long long mod = 1000000007;
long long d[5001][maxy];

int main()
{
	long long n, x;
	scanf("%lld", &n);
	
	vector<long long> input;
	while (n-- > 0)
	{
		scanf("%lld", &x);
		input.push_back(x);
	}

	sort(input.begin(), input.end());

	if (input[0] != 1)
	{
		printf("0");
		return 0;
	}

	d[0][0] = 1;
	d[0][1] = 1;

	long long above5000 = 0;
	
	int jmin = 0;
	for (int i = 1; i < input.size(); ++i)
	{
		long long value = input[i];	
		long long a5000 = 0;	

		for (int j = jmin; j < maxy; j++)
		{
			d[i][j] = (d[i][j] + d[i-1][j]) % mod;
			long long prev_score = d[i-1][j];	

			if (j >= value-1)
			{
				long long newValue = j + value;
				
				if (newValue >= maxy)
				{
					a5000 = (a5000 + prev_score) % mod;					
				}
				else
				{
                   d[i][newValue] = (d[i][newValue] + prev_score) % mod;					
				}
			}
		}

		above5000 = (above5000 * 2 + a5000) % mod;
	}

	long long score = above5000;

    for (int j = 1; j < maxy; j++)
    {
		score = (score + d[input.size()-1][j]) % mod;
	}

	printf("%lld", score);	
}