二项式反演的入门题，来写写理解。
( ext{Solution:})
题目大意：给定两个互不相同的数列 (a,b,) 令他们两两配对，求 (a>b) 的数量恰好比 (b>a) 的数量多 (k) 的方案数。
首先观察到如果满足这个条件那么其对数必然为 (frac{n+k}{2}) 个。所以可以把 (n+k) 是奇数的情况去掉。
考虑，如果我们直接设 (f[i][j]) 为前 (i) 个糖果恰好有 (j) 对大于另一种的，如何转移？
第一种是第 (i) 个糖果形成了符合条件的。观察一下，两个数列不单调？先排完序再继续考虑。
如果说需要形成第一种情况，那有多少种是可以配对的？
但是我们发现，如果这样假设，对应另一种的情况有多少对是不明确的。所以无法准确计算。
那么假设 (f[i][j]) 表示前 (i) 个选择了 (j) 对满足条件的方案数？
但我们还是需要得知前面的点有多少对凑成了另一种情况的点。同样不好求。
考虑另一种思路:设 (f[i][j]) 表示前 (i) 个，至少有 (j) 对是第一种情况。换句话说，我钦定了 (j) 对满足条件，而其他的还没有配对的方案数。
由于这里的定义是至少，所以其他的没有被钦定的点就可以随便排列。
先让其他点不匹配，直接把 (f) 求出来。那么 (f[i][j] imes (i-j)!) 就是方案数了。
由于其他点没有钦定，所以一定还有 (i-j) 种可以匹配。如果不匹配就直接放着就好了。
所以 (f[i][j]=cnt_i imes f[i-1][j-1]+f[i-1][j].)
考虑如何求出题目要求的 恰好 情况：用二项式反演。
容易发现，恰好的情况是可以被至少来容斥出来的。有：
容斥原理，或者叫做 二项式反演 。
于是我们再做一遍二项式反演即可。
一些细节：如果在 (g) 数组上直接反演，枚举的下标记得从 (i+1) 开始，因为你已经拿到了原来的值了，再加就重复了。
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
const int mod=1e9+9;
inline int Add(int x,int y){return (x+y)%mod;}
inline int Mul(int x,int y){return 1ll*x*y%mod;}
inline int Dec(int x,int y){return (x-y+mod)%mod;}
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline int Abs(int x){if(x<0)x=-x;return x;}
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=Mul(res,x);
x=Mul(x,x);y>>=1;
}
return res;
}
int f[N][N];
int g[N];
int inv[N],fac[N];
int n,k,a[N],b[N];
inline int C(int x,int y){
if(x<y)return 0;
return Mul(fac[x],Mul(inv[y],inv[x-y]));
}
void predo(){
fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=Mul(fac[i-1],i);
inv[n]=qpow(fac[n],mod-2);
for(int i=n;i;--i)inv[i-1]=Mul(inv[i],i);
}
inline int getpos(int x){
int l=1,r=n;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(b[mid]<x)ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
if((n+k)&1){
puts("0");
return 0;
}
predo();
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
sort(a+1,a+n+1);sort(b+1,b+n+1);
for(int i=0;i<=n;++i)f[i][0]=1;
for(int i=1;i<=n;++i){
int num=getpos(a[i]);
for(int j=1;j<=i;++j){
f[i][j]=Add(f[i][j],Add(Mul(f[i-1][j-1],Max(num-j+1,0)),f[i-1][j]));
}
}
for(int i=1;i<=n;++i)g[i]=f[n][i];
for(int i=1;i<=n;++i)g[i]=Mul(g[i],fac[n-i]);
int P=(n+k)/2;
for(int i=P+1;i<=n;++i){
g[P]=Add(g[P],Mul(Mul(qpow(mod-1,i-P),C(i,P)),g[i]));
}
printf("%d
",g[P]);
return 0;
}