如果你看不太懂二项式反演（比如我）
那么只需要记住：对于某两个$g(i),f(i)$
----------------------------
如果：$f(n)=\sum_{i=0}^{n}C(n,i)g(i)$
那么：$g(n)=\sum_{i=0}^{n}(-1)^{n-i}\ C(n,i)f(i)$
----------------------------
如果：$f(k)=\sum_{i=k}^{n}C(i,k)g(i)$
那么：$g(k)=\sum_{i=k}^{n}(-1)^{i-k}\ C(i,k)f(i)$
糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多k组。看起来很麻烦
设“药片”比“糖果”能量大的组数为$x$
$x+(x-k)=n$
解得$x=(n+k)/2$，所以$n+k$为奇数一定是没有方案的
现在问题转化成：“药片”比“糖果”能量大的组数为$(n+k)/2$的方案数
看看数据$O(n^2)$可过，想着搞个dp
先将$A[i],B[i]$小到大排好序
蓝后设$f[i][j]$表示（从小到大）扫到$A[i]$（第$i$个)，并配好$j$对的方案数
再预处理好$l[i]$表示$B$数组中有多少个数小于$A[i]$
分为不配对或配对的情况，列出方程
$f[i][j]=f[i-1][j]+max(0,l[i]-j+1)*f[i-1][j-1]$
$dp$完了，现在我们来考虑$f[n][i](0<=i<=n)$有啥用（大雾）
对于每个$f[n][i]$，剩下没配对的$n-i$个可以随便排序（注意随便排序可能又配出合法对，有重复计算）
于是我们设个$g(i)$表示$n$个数合法配对数$>=i$的排列方案数
$g(i)=f[n][i]*(n-i)!$
但是我们要求的是合法配对数$==i$的排列方案数鸭
设个$f(i)$表示所求↑↑↑
显然对于每个$g(k)\ and\ f(i)\ \ (i>=k)$
$g(k)$都加了$C(i,i-k)=C(i,k)$个$f(i)$进去
于是我们就得到了$g(k)$关于$f(i)$的表达式
$g(k)=\sum_{i=k}^{n}C(i,k)f(i)$
仔细一看，这不是可以套二项式反演吗！
$f(k)=\sum_{i=k}^{n}(-1)^{i-k}\ C(i,k)g(i)$
蓝后就可以愉快地把$f(k)$算出来辣
注意$mod=1e9+9$（不是$1e9+7$）TAT
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 2010
const ll P=1e9+;
int n,k,A[N],B[N],l[N];
ll f[N][N],g[N],inv[N],fac[N],ifac[N],ans;
void prep(){
inv[]=; fac[]=fac[]=ifac[]=ifac[]=;
for(ll i=;i<=n;++i){
inv[i]=(P-P/i)*inv[P%i]%P;
fac[i]=fac[i-]*i%P;
ifac[i]=ifac[i-]*inv[i]%P;
}
}
inline ll C(int a,int b){return fac[a]*ifac[b]%P*ifac[a-b]%P;}
int main(){
scanf("%d%d",&n,&k);
if((n+k)&){puts(""); return ;}
k=(n+k)/; prep();
for(int i=;i<=n;++i) scanf("%d",&A[i]);
for(int i=;i<=n;++i) scanf("%d",&B[i]);
sort(A+,A+n+); sort(B+,B+n+); int tmp=;
for(int i=;i<=n;++i){
while(tmp<n&&B[tmp+]<A[i]) ++tmp;
l[i]=tmp;
}f[][]=;
for(int i=;i<=n;++i){
f[i][]=f[i-][];
for(int j=;j<=i;++j)
f[i][j]=(f[i-][j]+1ll*(l[i]-j+)*f[i-][j-])%P;
}
for(int i=;i<=n;++i) g[i]=f[n][i]*fac[n-i]%P;
for(int i=k;i<=n;++i)
ans=((ans+1ll*(((i-k)&)?-:)*C(i,k)*g[i])%P+P)%P;
printf("%lld",ans);
return ;
}