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

using namespace std;

long long mod_inv(long long a, long long b, long long s0 = 1, long long s1 = 0) {
    return (b==0)? s0: mod_inv(b, a%b, s1, s0 - s1*(a/b));
}

int main() {
    int n; cin >> n;
    long long p = 1000000009LL;
    vector<long long> a(n), inv(n+1, 0);

    // Read and sort the input.
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());

    // Precompute modular inverses for convenience.
    for(long long i = 1; i <= n; i++) {
        inv[i] = (mod_inv(i, p) + p) % p;
    }
    for(int i = 0; i <= n; i++) {
        cerr << inv[i] << endl;
    }

    // perm[k][l] contains the number of distinct permutations of 
    // a[k], ..., a[l-1].
    vector<vector<long long>> perm(n+1, vector<long long>(n+1, 0));
    for(int k = 0; k <= n; k++) {
        perm[k][k] = 1;
        int ct;

        for(long long l = k + 1; l <= n; l++) {
            if(l > k + 1 && a[l-2] == a[l-1])
                ct++;
            else
                ct = 1;

            perm[k][l] = (perm[k][l-1]*(l-k) *inv[ct]) % p;
        }
    }

    // eus[k] is the number of entirely unordered sequences we can make out of
    // the first k elements of the input (in ascending order).
    vector<long long> eus(n+1);
    eus[0] = 1;
    for(int k = 1; k <= n; k++) {
        // A k element sequence which is not entirely unsorted has a first
        // sorted element, and we count them by the position of that first
        // element. The elements before that are entirely unsorted, and the
        // elements after are in any order.
        //
        // Then we just subtract the unentirely unsorted sequences from all
        // sequences we can make out of the first k elements, to get the
        // entirely unsorted ones.

        eus[k] = perm[0][k];
        for(int i = 0; i < k; i++) {
            eus[k] -= (eus[i] * perm[i+1][k]) % p;
            eus[k] = eus[k] % p;
            if(eus[k] < 0)
                eus[k] += p;
        }
    }

    cout << eus[n] << endl;
    return 0;
}