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

using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;

constexpr ll MOD = 1e9+9;

int main() {
	int n;
	cin >> n;
	vi A(n);
	for (ll &a : A) cin >> a;
	sort(A.begin(), A.end());

	// Inverses
	vi I(n+1, 1LL);
	for (int i = 2; i <= n; ++i)
		I[i] = (MOD - (MOD/i) * I[MOD%i] % MOD) % MOD;

	// Total amount of sequences over [l, r]
	vvi T(n, vi(n, 1LL));
	for (int i = 0; i < n; ++i)
		for (int j = i+1, eq = 1; j < n; ++j)
			eq = (A[j] == A[j-1] ? eq+1 : 1),
			T[i][j] = T[i][j-1] * ll(j-i+1) % MOD * I[eq] % MOD;

	// Unsorted sequences over [0..n]
	vi U(n, 0LL);
	for (int i = 1; i < n; ++i) {
		U[i] = T[0][i];
		for (int j = 0; j <= i; ++j)
			U[i] = (MOD*MOD + U[i]
					- (j>0?U[j-1]:1LL) * (j<i?T[j+1][i]:1LL)) % MOD;
	}

	cout << U[n-1] << endl;

	return 0;
}