import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

public class EntirelyUnsortedSequences_HarryACC {

	static long mod = 1000000009;
	static long[] dp; // Entirely unsorted sequences made from the interval [0, i).
	static long[][] perms; // Number of permutations of the sequence with indices in [i, j).
	static long[] inv;
	
	
	static long inv(long x)
	{
		return pow(x, mod-2);
	}

	static long pow(long x, long y)
	{
        if (y == 0) return 1;

        long p = pow(x, y / 2) % mod;
        p = (p * p) % mod;

        if (y % 2 == 0) return p;
        else return (x * p) % mod;
	}

	static long gcd(long a, long b)
	{
		if(a == 0) return b;
		return gcd(b%a, a);
	}



	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		dp = new long[n+1];
		perms = new long[n+1][n+1];
		inv = new long[n+1];
		ArrayList<Integer> a = new ArrayList<Integer>();

		long[] fact = new long[n+1];
		fact[0] = 1;


		for(int i = 0; i < n; i++)
			a.add(sc.nextInt());

		for(int i = 1; i <= n; i++)
			fact[i] = (fact[i-1] * i) % mod;
		
		for(int i = 1; i <= n; i++)
			inv[i] = inv(i);

		Collections.sort(a);

		for(int i = 0; i <= n; i++)
		{
			HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
			perms[i][i] = 1;

			for(int j = i+1; j <= n; j++)
			{
				long t = (perms[i][j-1] * (j - i)) % mod;
				if(hash.containsKey(a.get(j-1)))
				{
					int u = hash.get(a.get(j-1));
					t = (t * inv[u + 1]) % mod;
					hash.replace(a.get(j-1), u + 1);
				}
				else hash.put(a.get(j-1), 1);

				perms[i][j] = t;
			}

		}

		dp[0] = 1;
		dp[1] = 0;

		for(int k = 2; k <= n; k++)
		{
			dp[k] = perms[0][k];
			for(int i = 0; i < k; i++) // The "pivot".
			{
				long rem = (dp[i] * perms[i+1][k]) % mod;
				dp[k] = (dp[k] - rem + mod) % mod;
			}
		}

		System.out.println(dp[n]);

	}

}