求解方案数，并且要求对一个很大的数取模，首先排除玄学做法。

这种问题通常考虑数学做法或者 dp 做法，此处因为存在数组大小的限制，很难以使用数学做法，于是我们考虑使用 dp 解决这个问题。

考虑如何定义状态：显然应该记录现在匹配了几个。

这够了吗？不太够，我们应该还需要记录匹配到哪里了，否则会反复选择同一对。

于是得到一个定义：$dp[now][i][j]$ 代表选择了 $now$ 个数，两个数组分别匹配到 $i$ 和 $j$ 的方案数。

此时我们考虑如何转移。

有两种情况：选择或者不选择。

如果是选择，判断其满足条件后加上就好了。

如果是不选择，我们需要从前面累加答案。

显然不选择的情况可以在处理选择的情况后前缀和处理，当然使用数据结构也是可行的。

对于选择，这是很好处理的，具体实现下来长这样：

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
        if(a[i]>b[j]) dp[x][i][j]=dp[x-1][i-1][j-1];//选择一组新的

然后前缀和一下就可以解决这个问题了。

算一下实现复杂度：$O(nmk)$，可以过。

但是毕竟可以滚动数组优化，秉着养成好习惯的原则，再用滚动数组优化一下：

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+5,Mod=1e9+9;
int dp[3][N][N],a[N],b[N];

inline int read(){
	int s=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s;
}

int main(){
    int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++) b[i]=read();
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++) dp[0][i][j]=1;
	for(int now=1;now<=k;now++){
		int x=now&1,y=(now+1)&1;//滚动数组 
	    for(int i=0;i<=n;i++)
		    for(int j=0;j<=m;j++) dp[x][i][j]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++) 
			    if(a[i]>b[j]) dp[x][i][j]=dp[y][i-1][j-1];//选择一组新的 
		for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) dp[x][i][j]=(dp[x][i][j]+dp[x][i][j-1])%Mod;//FJ空过 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) dp[x][i][j]=(dp[x][i][j]+dp[x][i-1][j])%Mod;//FP空过 
	} 
	cout<<dp[k&1][n][m];
	return 0;
}