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
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 5;
const int M = 1e9 + 7;

int cuk[N];
int ile[N];
long long kombinacje[N][N];
pair <int, pair <int, int> > pref[N]; //suma na prefiksie, liczba w cuk do jakiej to sie odwoluje, nr z kolei tej liczby

int n;

long long power(long long podstawa, long long wykladnik){
	if(wykladnik == 0){
		return 1;
	}
	if(wykladnik % 2 == 0){
		long long w = power(podstawa, wykladnik / 2);
		return (w % M * (w % M)) % M;
	}
	else{
		return (podstawa % M * (power(podstawa, wykladnik - 1) % M)) % M;
	}	
}

long long silnia(int a, int x){
	long long licznik = 1, mianownik = 1;
	for(int i = 1; i <= x; i++){
		mianownik *= i;
		mianownik %= M;
	}
	
	int pocz = max(a - x, 1);
	for(int i = pocz; i <= a; i++){
		licznik *= i;
		licznik %= M;
	}
	
	return (licznik % M * (power(mianownik, M - 2) % M)) % M;
}

int binsearch(int p, int k, int x){
	int m = (p + k) / 2;
	while(p < k){
		if(pref[m].first < x) p = m + 1;
		else k = m;
		m = (p + k) / 2;
	}
	return p;
}

long long przelicz(int dl){
	long long wynik = 0;
	int prefiks = 0;
	for(int i = 1; i <= dl; i++){
		if(cuk[i] == 1){
			for(int j = 1; j <= ile[1]; j++){
				kombinacje[1][j] += silnia(ile[1], j);
				kombinacje[1][j] %= M;
				wynik += kombinacje[1][j];
				wynik %= M;
				pref[++prefiks] = make_pair(j, make_pair(1, j));
			}
			continue;
		}
		
		int a = cuk[i];
		if(pref[prefiks].first < a - 1){
			//cout << "out " << a << "\n";
			return wynik % M;
		}
		
		int poz = binsearch(1, prefiks, a - 1);
		int k = prefiks;
		
		for(int j = 1; j <= ile[a]; j++){
			long long komb = silnia(ile[a], j);
			//cout << a << " komb: " << komb << "\n";
			for(int l = poz; l <= k; l++){
				//cout << "l: " << l << "\n";
				kombinacje[a][j] += ((komb % M) * (kombinacje[pref[l].second.first][ile[pref[l].second.first] - pref[l].second.second + 1]) % M) % M;
			}
			wynik += kombinacje[a][j];
			wynik %= M;
			pref[++prefiks] = make_pair(pref[prefiks].first + a, make_pair(a, j));
		}
	}
	return wynik % M;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	
	int poz = 1;
	
	for(int i = 1; i <= n; i++){
		long long a;
		cin >> a;
		if(ile[a] == 0) cuk[poz++] = a;
		ile[a]++;
	}
	
	sort(cuk + 1, cuk + poz);
	
	cout << przelicz(poz) % M;
	
	/*for(int i = 1; i <= 7; i++){
		for(int j = 1; j <= 7; j++){
			cout << "\n" << "komb " << i << " " << j << " " << kombinacje[i][j];
		}
	}*/
	
	/*for(int i = 1; i <= n; i++){
		cout << pref[i].first << " " << pref[i].second.first << " " << pref[i].second.second << "\n"; 
	}*/
}