#define _GLIB_CXX
#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;
}

int main(){
	int n; cin >> n;
	V a(n), inv = inverses(n);
	vector<V> c(n+1, V(n+1, 1));
	for(auto &x:a) cin >> x;
	sort(a.begin(), a.end());
	for(int i = 0; i < n; ++i)
		for(int j = i; j <= n; ++j)
			for(int k = i+1, l=1; k < j; ++k)
				c[i][j] = c[i][j] * (k-i+1) % M * inv[l=a[k]==a[k-1]?l+1:1] % M;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j < i; ++j)
			c[0][i] -= c[0][j] * c[j+1][i] % M;
		c[0][i] %= M;
	}
	cout << (c[0][n]+M)%M << endl;
}