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

using namespace std;
using V = vector<long long>;
using I = V::const_iterator;

constexpr long long M = 1e9+9;

int gcd(int a, int b){ return b==0 ? a : gcd(b, a%b);}

template<typename I>
V count(I b, I e){
	long long n = e-b, c=0, v=-1;
	V cs(n+1, 1), d(n), prefix(n+1,1);
	iota(d.begin(), d.end(), 1);
	for(int i = 0; i < n; ++i, ++b){
		*b == v ? ++c : (v=*b, c=1);
		long long t = c, g, j = i, bad = max(i,1);
		for(; j >= 1 && t > 1; --j)
			if((g = gcd(d[j], t)) > 1) d[j] /= g, t/=g, bad=j;
		for(int j = bad; j <= i; ++j)
			prefix[j] = prefix[j-1] * d[j] % M;
		cs[i+1] = prefix[i];
	}
	return cs;
}

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