#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5000;
const ll mod = 1e9 + 9;

int pascal[maxn+1][maxn+1];

int main()
{
	// binomial coefficients
	for (int i = 0; i <= maxn; i++) {
		pascal[i][0] = pascal[i][i] = 1LL;
		for (int j = 1; j < i; j++) {
			pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
			if (pascal[i][j] >= mod)
				pascal[i][j] -= mod;
		}
	}

	// read input, compress data
	int N;
	cin >> N;
	vector<int> X(N), A;
	for (int i = 0; i < N; i++) cin >> X[i];
	sort(X.begin(), X.end());

	for (int i = 1, len = 1; i <= N; i++) {
		if (i == N || X[i] != X[i - 1]) {
			A.push_back(len);
			len = 1;
		} else len++;
	}
	int na = A.size();

	// determine total number of sequences
	vector<ll> seqs(N+1, 0);
	seqs[0] = 1; // empty sequence

	int elems = 0;
	ll combs = 1LL;

	for (int m : A) {
		for (int i = 1; i <= m; i++) {
			seqs[elems + i] = combs * pascal[elems + i][i] % mod;
		}
		elems += m;
		combs = combs * pascal[elems][m] % mod;
	}

	vector<int> sums(na+1,0);
	vector<ll> eus(N+1,0);
	eus[0] = 1;
	for (int i = 0, sum = 0; i < na; i++) {
		for (int j = 1; j <= A[i]; j++) {
			ll ans = 0LL;

			// iterate over all the possible indices for the *first* sorted point.

			// begin in the back:
			for (int j2 = j; --j2 >= 0; ) {
				// only one combination: putting same valued after the sorted point
				ans += eus[sum + j2];
				//if (ans >= mod) ans -= mod;
			}

			elems = j;
			combs = 1LL;

			// work backwards:
			for (int i2 = i; --i2 >= 0;  ) {
				for (int j2 = 1; j2 <= A[i2]; j2++) {
					int nright = elems + j2 - 1;
					int nleft = sum + j - nright - 1;
					// put elems + j2 to the right of this current element.
					// then there are sum + j - (elems + j2) - 1 elements to the left.
					ll part = combs * pascal[nright][j2 - 1] % mod;
					ans += eus[nleft] * part % mod;
					if (ans >= mod) ans -= mod;
				}
				elems += A[i2];
				combs = combs * pascal[elems][A[i2]] % mod;
			}

			ans = seqs[sum + j] - ans;
			if (ans < 0) ans += mod;
			eus[sum + j] = ans;
		}
		sum += A[i];
	}

	cout << eus[N] << endl;
	return 0;
}