对于这道题，首先每个人的位置并不影响结果 所以我们可以将相同颜色糖果的人放在一块处理

设 \(f_{i,j}\) 表示处理到第 \(i\) 种糖果至少有 \(j\) 人的糖果和原先的类型相同 枚举当前种类中不满足要求的个数 则有

\(c_i\) 表示第 \(i\) 种糖的个数，这里之所以要乘上 \((c_i-k)!\) 的逆元 是因为我们还不确定这些人究竟是否满足要求 先将它们的顺序除去 在最后统计时我们再给所有剩下的人分配一个糖果即可 结果当然要容斥一下啦~~

#include<bits/stdc++.h>

using namespace std;

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define pa pair<int,int>

#define mod 1000000009

#define ll long long

#define mk make_pair

#define pb push_back

#define fi fisrt

#define se second

#define cl(x) memset(x,0,sizeof x)

#ifdef Devil_Gary

#define bug(x) cout<<(#x)<<" "<<(x)<<endl

#define debug(...) fprintf(stderr, __VA_ARGS__)

#else

#define bug(x)

#define debug(...)

#endif

const int INF = 0x7fffffff;

const int N=2e3+5;

/*

char *TT,*mo,but[(1<<15)+2];

#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/

inline int read(){

    int x=0,rev=0,ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return rev?-x:x;

}

int n,ans,tot,f[N][N],col[N],bin[N],inv[N];

void init(){

	bin[0]=bin[1]=inv[0]=inv[1]=1;

	for(int i=2;i<=n;i++) bin[i]=(ll)bin[i-1]*i%mod,inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;

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

}

int C(int n,int m){

	return (ll)bin[n]*inv[n-m]%mod*inv[m]%mod;

}

int main(){

#ifdef Devil_Gary

	freopen("in.txt","r",stdin);

#endif

	n=read(),init(),f[0][0]=1;

	for(int i=1;i<=n;i++) col[read()]++;

	for(int i=1;i<=n;tot+=col[i++]) for(int k=0;k<=col[i];k++) {

		int tmp=(ll)C(col[i],k)*inv[col[i]-k]%mod;

		for(int j=0;j<=tot;j++)

		f[i][j+k]=(f[i][j+k]+(ll)f[i-1][j]*tmp%mod)%mod; 

	}

	for(int i=0;i<=n;i++) ans=(ans+(ll)((i&1)?mod-1:1)*f[n][i]%mod*bin[n-i]%mod)%mod;

	return !printf("%d\n",ans);

}