发现难以维护差值，于是令 \(K=\frac{n+k}2\)，这样就把问题转化为了“糖果”比“药片”大的组数为 \(K\) 的情况有多少种。
设 \(dp_{i,j}\) 表示我们用前 \(i\) 个“糖果”和“药片”配对，至少有 \(j\) 组“糖果”比“药片”大，有多少种情况；\(c_i\) 表示有多少个“药片”比第 \(i\) 个糖果小。
我们对“糖果”和“药片”分别排序，显然有：
\[f_{i,j}=f_{i-1,j}+(c_i-j+1)f_{i-1,j-1} \]然后就是简单二项式反演了。设 \(g_i\) 表示恰好只有 \(i\) 组“糖果”比“药片”大，那么就有：
\[g_K=\sum_{i=K}^n(-1)^{i-K}\binom iKf_{n,i} \]时间复杂度 \(O(n^2)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005,p=1e9+9;
int n,C[N][N],jc[N],ans;
int k,a[N],b[N],dp[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k,jc[0]=1;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i],jc[i]=jc[i-1]*i%p;
if((n+k)%p==0) cout<<0,exit(0);
k=(n+k)/2,dp[0][0]=1;
sort(a+1,a+n+1),sort(b+1,b+n+1);
for(int i=0;i<=n;C[i++][0]=1)
for(int j=1;j<=min(i,k);j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
for(int i=1,sum=0;i<=n;dp[i++][0]=1){
while(sum<n&&b[sum+1]<a[i]) sum++;
for(int j=1;j<=min(i,sum);j++)
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*(sum-j+1))%p;
}for(int i=k,opt=1;i<=n;i++,opt=-opt)
ans=(ans+opt*C[i][k]*jc[n-i]%p*dp[n][i])%p;
cout<<(ans+p)%p;
return 0;
}