我有一份代码没特判 n+k 为奇数（此时答案为 0）的情况，在 n+k 为奇数的数据中这份代码不一定会得到 0，但还是 AC 了。

#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=2005,P=1e9+9;
int n,k,a[MAXN],b[MAXN],c[MAXN][MAXN],f[MAXN][MAXN],g[MAXN],fac[MAXN],ans;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=(long long)fac[i-1]*i%P;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	for(int i=1;i<=n;++i)
		cin>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1,j=1;i<=n;g[i++]=j)
		while(j<=n&&a[i]>b[j])
			++j;
	f[0][0]=c[0][0]=1;
	for(int i=1;i<=n;c[i][0]=f[i][0]=1,++i)
		for(int j=1;j<=i;++j){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
			f[i][j]=(f[i-1][j]+(long long)f[i-1][j-1]*(g[i]-j))%P;
		}
	k=n+k>>1;
	for(int i=k;i<=n;i+=2)
		ans=(ans+(long long)c[i][k]*f[n][i]%P*fac[n-i])%P;
	for(int i=k+1;i<=n;i+=2)
		ans=(ans-(long long)c[i][k]*f[n][i]%P*fac[n-i])%P;
	cout<<(ans+P)%P;
	return 0;
}