#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1000000009 ;

int n, m;

ll ans;

int col[2010], s[2010], v[2010];

ll c[2010][2010], f[2010][2010], jc[2010], ine[2010], jcc[2010];

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0, f = 1;

	char c = nc();

	while (c < 48) {

		if (c == '-')

			f = -1;

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x * f;

}

int main() {

    n = rd();

    for (int i = 0; i <= n; i ++ ) {

        c[i][0] = 1;

        for(int j = 1; j <= i; j ++ ) {

			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;

		}

    }

    jc[0] = ine[0] = jcc[0] = jc[1] = ine[1] = jcc[1] = 1;

    for (int i = 2; i <= n; i ++ ) {

        jc[i] = (ll)jc[i - 1] * i % mod;

		ine[i] = mod - (mod / i) * ine[mod % i] % mod;

		jcc[i] = (ll)jcc[i - 1] * ine[i] % mod;

    }

    for (int i = 1; i <= n; i ++ ) {

		col[i] = rd();

	}

    sort(col + 1, col + n + 1);

    for (int i = 1; i <= n; i ++ ) {

        if (col[i] > col[i - 1]) {

			m ++ ;

		}

		v[m] ++ ;

    }

    for(int i = 1; i <= m; i ++ ) {

		s[i] = s[i - 1] + v[i];

	}

    f[0][0] = 1;

    for (int i = 1; i <= m; i ++ ) {

		for (int j = 0; j <= s[i - 1]; j ++ ) {

			for (int k = 0; k <= v[i]; k ++ ) {

        		f[i][j + k] = (f[i][j + k] + (ll)f[i-1][j] * c[v[i]][k] % mod * jc[v[i]] % mod * jcc[v[i] - k] % mod) % mod;

			}

		}

	}

    for (int i = 0; i <= n; i ++ ) {

        ans = (ans + (ll)((i & 1) ? -1 : 1) * f[m][i] * jc[n - i] + mod) % mod;

    }

    for (int i = 1; i <= m; i ++ ) {

		ans = (ll)ans * jcc[v[i]] % mod;

	}

	cout << ans << endl ;

    return 0;

}