若
\[g_n = \sum_{i=0}^n\dbinom{n}{i}f_n \]有
\[f_n=\sum_{i=1}^{n}\dbinom{n}{i}g_n \]若
\[g_i=\sum_{j=i}^{n} \dbinom{j}{i}f_j \]则
\[f_i=\sum_{j=i}^{n}\dbinom{j}{i}(-1)^{j-i}g_j \]给两个数列 \(a\), \(b\), 要求 \(a_i,b_i\) 两两匹配，使得 \(a_i>b_i\) 的个数减去 \(a_i<b_i\) 的个数等于 \(k\)，求总方案数。
先将 \(a,b\) 排序，定义 \(f_{i,j}\) 为前 \(i\) 个 \(a[i]\) 中恰好有 \(j\) 个满足 \(a_i>b_i\) 的方案数，其他的均未匹配的方案数。
有 \(f_{i,j} = f_{i-1,j} + f_{i-1,j-1}(r_i-(j-1))\) 。
其中 \(r_i\) 为 \(b\) 中小于 \(a_i\) 的个数。
定义 \(g_i\) 为满足 \(a_j>b_j\) 的个数大于 \(i\) 的方案数， \(G_i\) 表示满足 \(a_j>b_j\) 的个数等于 \(i\) 的方案数。
可以发现 \(G_i\) 在 \(g_j\) （\(i>j\)）中出现了 \(\tbinom{i}{j}\) 次。
有
\[g_i=f_{n,i}(n-i)! \]\[g_i = \sum_{j=i}^{n}\dbinom{j}{i}G_j \]\[G_i = \sum_{j=i}^{n}\dbinom{j}{i}(-1)^{j-i}g_j \]#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline ll Max(ll x, ll y){return x > y ? x : y;}
const ll N = 2001;
const ll mod = 1e9 + 9;
ll n, c[N][N], f[N][N], g[N], a[N], b[N], mx[N], fac[N];
void init_c(ll tt){
c[0][0]=1;
for(ll i = 1; i <= tt; i++){
c[i][0]=1;
for(ll j = 1; j <= tt; j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
}
void init_fac(ll tt){
fac[0] = 1;
for(ll i = 1; i <= tt; i++)
fac[i] = fac[i-1] * i % mod;
}
ll fu(ll x){return x&1?-1:1;}
int main(){
ll k;
cin>>n>>k;
for(ll i = 1; i <= n; i++)
cin >> a[i];
for(ll i = 1; i <= n; i++)
cin >> b[i];
sort(a+1, a+n+1);
sort(b+1, b+n+1);
init_c(n);
init_fac(n);
f[0][0]=1;
for(ll i = 1; i <= n; i++){
mx[i] = lower_bound(b+1, b+n+1, a[i]) - b - 1;
f[i][0] = f[i-1][0];
for(ll j = 1; j <= i; j++)
f[i][j] = (f[i-1][j] + f[i-1][j-1] * Max(0, (mx[i] - j + 1)) % mod) % mod;
}
ll x = (n + k) >> 1;
if((n+k)%2)cout<<0<<endl, exit(0);
ll ans = 0;
for(ll i = x; i <= n; i++)
ans = (ans + fu(i-x) * c[i][x] % mod * f[n][i] % mod * fac[n-i] % mod) % mod;
cout << (ans % mod + mod) % mod << endl;
return 0;
}