感觉没什么问题啊（）

#include <bits/stdc++.h>

using namespace std;

namespace liuzimingc {
const int N = 2e3 + 5, MOD = 1e9 + 9;
#define int long long
#define endl '\n'

int n, a[N], m, fac[N], inv[N], ans, col[N], f[N][N];

int qkpow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ans;
}

int C(int n, int m) {
	return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int A(int n, int m) {
	return fac[n] * inv[n - m] % MOD;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], col[a[i]]++;
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
	inv[n] = qkpow(fac[n], MOD - 2);
	for (int i = n - 1; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
	f[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		m += col[i];
		for (int j = 0; j <= m; j++)
			for (int k = 0; k <= col[i]; k++)
				(f[i][j] += f[i - 1][j - k] * C(col[i], k) % MOD * A(col[i], k) % MOD) %= MOD;
	}
	for (int i = 0; i <= n; i++) {
		int sgn = i & 1 ? -1 : 1;
		ans = (ans + f[n][i] * fac[n - i] % MOD * sgn + MOD) % MOD;
	}
//	cout << ans << endl;
	for (int i = 1; i <= n; i++) ans = ans * inv[col[i]] % MOD;
	cout << ans << endl;
	return 0;
}
#undef int
}

int main() {
	liuzimingc::main();
	return 0;
}