14165

#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];
}