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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <stdlib.h>

#define mod 1000000007

using namespace std;

int newton[5005][5005];

void policz_newton(int n)
{
	newton[0][0]=1;
	for (int i=1; i<n; i++)
	{
		newton[i][0]=1;
		for (int j=1; j<=i; j++)
			newton[i][j] = (newton[i-1][j]+newton[i-1][j-1])%mod;
	}

//	for (int i=0; i<n; i++)
//	{
//		for (int j=0; j<=i; j++) cout << newton[i][j] << " ";
//		cout << endl;
//	}

}


int compare(const void* a, const void* b)
{
	const int* x = (int*) a;
	const int* y = (int*) b;
	if (*x > *y)
		return 1;
	else if (*x < *y)
		return -1;
	return 0;
}

int main() 
{
	int n;
	int a[5005];
	int i,j,k;
	int sumy[5005];
	int ile[5005];
	int t[5005];
	int max = 0;
	int wynik;
	
	cin >> n;
	a[0]=0;
	for (i=1; i<=n; i++) cin >> a[i];
	policz_newton(n);
	for (i=0; i<n; i++) if (max<a[i]) max = a[i];
	for (i=1; i<=max; i++) t[i]=0;
	for (i=0; i<n; i++) t[a[i]]++;
	
	qsort(a,n+1,sizeof(int),compare);
	
	ile[0]=1;
	sumy[0]=0;
	
	for (i=1; i<=n; i++)
	{
		sumy[i]=sumy[i-1]+a[i];
		
		j=i;
		ile[i]=0;
		while (j-->0 && sumy[j]>=a[i]-1) ;
		j++;
	
		k=0;
		while (j<i && a[j]==a[j-1]) 
		{
			ile[i]=(ile[i]+newton[t[a[j]]][k])%mod; 
//			cout << t[a[j]] << " " << k << " " << newton[t[a[j]]][k] << endl;
			j++;
			k++;
		}

		//if (j>0 && a[j]==a[j-1])
		//{
		//	k=j;
		//	while (a[k-1]==a[j]) k--;
		//	while (a[j]==a[k]) 
		//	{
		//		ile[i]=(ile[i]+ile[k])%mod;
		//		j++;
		//		k++;
		//	}
		//}
		while (j<i) ile[i]=(ile[i]+ile[j++])%mod;
		if (ile[i]==0) break;
	}
	
	wynik = 0;
	for (i=1; i<=n; i++) wynik=(wynik+ile[i])%mod;
	
//	for (i=0; i<=n; i++) cout << sumy[i] << " " ; cout << endl;
//	for (i=0; i<=n; i++) cout << a[i] << " " ; cout << endl;
//	for (i=0; i<=n; i++) cout << ile[i] << " " ; cout << endl;
	
	cout << wynik%mod;
	
//	for (i=0; i<n; i++) if (max<a[i]) max = a[i];
//	for (i=1; i<=max; i++) t[i]=0;
//	for (i=0; i<n; i++) t[a[i]]++;
//	for (i=1; i<=max; i++) cout << t[i] << " " ; cout << endl;
	

	
	return 0;
}