输入的2*n个数字保证全不相同。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int Mod=1e9+;

int C[maxn][maxn],f[maxn][maxn],a[maxn],b[maxn],jc[maxn],ans;

int main()

{

    int N,K; scanf("%d%d",&N,&K);

    jc[]=; rep(i,,N) jc[i]=(ll)jc[i-]*i%Mod;

    rep(i,,N){

        C[i][]=;

        rep(j,,i) C[i][j]=(C[i-][j]+C[i-][j-])%Mod;

    }

    rep(i,,N) scanf("%d",&a[i]);

    rep(i,,N) scanf("%d",&b[i]);

    sort(a+,a+N+) ;sort(b+,b+N+);

    f[][]=;

    rep(i,,N){

        int pos=upper_bound(b+,b+N+,a[i])-b; pos--;

        rep(j,,i){

            f[i][j]=(f[i-][j]+(ll)f[i-][j-]*max(pos-j+,)%Mod)%Mod;

        }

        f[i][]=f[i-][];

    }

    if((N+K)%==) return puts(""),;

    K=(N+K)/;

    rep(i,K,N){

        f[N][i]=(ll)f[N][i]*jc[N-i]%Mod;

        if((i-K)&) ans=((ans-(ll)f[N][i]*C[i][K]%Mod)%Mod+Mod)%Mod;

        else ans=(ans+(ll)f[N][i]*C[i][K]%Mod)%Mod;

    }

    printf("%lld\n",(ans%Mod+Mod)%Mod);

    return ;

}