#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <iomanip>
#include <regex>
#include <numeric>
using namespace std;
#define pii pair<long long , long long>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const long long MAX = 100005;
const long long MOD = 1000000009;
int n, m, k;
long long arr1[1005], arr2[1005];
long long dp[1005][1005];
long long dp2[1005][1005];
void do_dp(){
memset(dp2, 0, sizeof dp2);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(arr1[i] > arr2[j]){
dp2[i][j] = dp[i - 1][j - 1];
}
}
}
}
void update_dp(){
for(int i = 0; i < 1005; i++){
for(int j = 0; j < 1005; j++){
dp[i][j] = dp2[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
dp[i + 1][j + 1] += dp[i][j + 1];
dp[i + 1][j + 1] += dp[i + 1][j];
dp[i + 1][j + 1] -= dp[i][j];
dp[i + 1][j + 1] %= MOD;
}
}
}
int main() {
//freopen("talent.in", "r", stdin);
//freopen("talent.out", "w", stdout);
FAST;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
cin >> arr1[i];
}
sort(arr1 + 1, arr1 + n + 1);
for(int i = 1; i <= m; i++){
cin >> arr2[i];
}
sort(arr2 + 1, arr2 + m + 1);
fill(&dp[0][0], &dp[0][0] + 1005 * 1005, 1);
for (int i = 0; i < k; i++)
{
do_dp();
update_dp();
}
while(dp[n][m] < 0){
dp[n][m] += MOD;
}
cout << dp[n][m];
}