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
#include <iostream>
#include <vector>
using namespace std;

#define FORE(x, b, e) for(int x = b; x <= (e); ++x)
#define FORL(x, b, e) for(int x = b; x <  (e); ++x)

#define P(x) cout <<#x <<'=' <<(x) <<" ";
#define PP cout <<endl;
#define Pv(x,a,b) cout << #x<<'=';for(int i=a;i<=b;i++)cout<<' '<<x[i];PP
#define Pvv(x,y,a,b) cout <<#x <<#y <<'=';FORE(i,a,b)cout<<' '<<x[y[i]];PP


typedef          long long  INT;
typedef unsigned long long UINT;
UINT MOD = 1000000007ULL;
#define MAX 5010

//------------------------------------------------------

INT mFact[MAX+1], iFact[MAX+1];

void initFact(int c) {
	UINT mInverse[c+1];

	mInverse[1] = 1;
	for (int i=2; i<=c; ++i)
		mInverse[i] = (MOD - (MOD/i) * mInverse[MOD%i] % MOD) % MOD;

	mFact[0]=1;
	iFact[0]=1;
	for(int i=1; i<=c; i++) {
		mFact[i] =  mFact[i-1] * i % MOD;
		iFact[i] =  iFact[i-1] * mInverse[i] % MOD;
	}
	
}

INT mBinomial(int m, int n) {
	return  ( mFact[m] * iFact[n] % MOD * iFact[m-n] % MOD );
}

//------------------------------------------------------

int cnt[MAX+2], Nactive=1, active[MAX+2], last[MAX+2];
INT Gsum[MAX+2]={1}, Isum[MAX+2];
	
void obl(const int nr, const int amax){
	
	for(int i=0; i<Nactive; i++ ) {
		int n = active[i];
		INT s = Gsum[n];
		if ( ((nr-n)>1) || (!s) ) {
			active[i] = active[--Nactive];
			--i;
		} else {
			Isum[i] = s;
			last[n] = nr;
		}
	}

	int Na=Nactive, m=cnt[nr],  d=0, x;
	INT b, v;
	for(int n=1; n<=m; n++) {
		b = mBinomial(m,n);
		d += nr;
		for(int i=0; i<Nactive; i++ ) {
			int act = active[i];
			x = min(amax+1, d+act );
			v = Gsum[x];
			if ((!v) && (last[x]<nr)) {
			  last[x] = nr;
			  active[Na] = x;
			  ++Na;
			} 
			Gsum[x] = (( b * Isum[i] % MOD) + v ) % MOD;
		}
	}

	Nactive = Na;
	return;
}

int main()
{
	std::ios_base::sync_with_stdio(false);  cin.tie(NULL);
	
	int n,a,amax=0, cmax=0;	

	cin >>n;
	for(int i=0; i<n; i++) { 
		cin >>a;
		amax=max(amax,a);
		cmax=max(cmax,++cnt[a]);
	}

	initFact(cmax+1);
	amax++;

	for(int i=1; (i<=amax)&&Nactive; i++)  
		if (cnt[i]) {
			obl(i, amax);
		}

	INT Sum=0;
	for(int i=1; i<=(amax+1); i++ ) Sum=(Sum+ Gsum[i])%MOD;
	cout <<(Sum%MOD) <<endl;
	
	return 0;
}