#include <algorithm>
#include <cassert>
#include <numeric>
#include <map>
#include <iostream>
#include <vector>

using namespace std;
using V = vector<long long>;

constexpr long long M = 1e9+9;

V inverses(int n){
	const int N = 5000;
	V prefix(N+1), suffix(N+1), inv(n+1);
	prefix[0] = prefix[1] = 1;
	for(int i = 2; i <= N; ++i)
		prefix[i] = prefix[i-1] * (i-1) % M;
	suffix[N] = 456105687; // (N+1) * ... * (M-1) % M
	for(int i = N-1; i >= 0; --i)
		suffix[i] = suffix[i+1] * (i+1) % M;
	for(int i = 1; i <= n; ++i)
		inv[i] = (- prefix[i] * suffix[i] % M + M)%M;
	return inv;
}

template<typename I>
void count(I b, I e, const V& inv, V& cs){
	for(int i = 1, c=0, v=-1; b!=e; ++i, ++b)
		cs[i] = cs[i-1] * i % M * inv[*b==v ? ++c : (v=*b, c=1)] % M;
}

int main(){
	int n; cin >> n;
	V a(n), inv = inverses(n), sc(n+1, 1), dp(n+1,1);
	for(auto &x:a) cin >> x;
	sort(a.begin(), a.end());
	count(a.begin(), a.end(), inv, dp);
	for(int i = 1; i <= n; ++i){
		count(a.rbegin()+n-i, a.rend(), inv, sc);
		for(int j = 0; j < i; ++j)
			dp[i] -= dp[j] * sc[i-j-1] % M;
		dp[i] %= M;
	}
	cout << (dp[n]+M)%M << endl;
}