#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1212], b[1212];
long long D[1212][1212][11];
long long mod = 1e9 + 9;
int main() {
	int n, m, k, i, j, p;
	scanf("%d%d%d", &n, &m, &k);
	for (i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (i = 1; i <= m; i++)scanf("%d", &b[i]);
	sort(a + 1, a + 1 + n); sort(b + 1, b + m + 1);
	for (i = 0; i <= n; i++)for (j = 0; j <= m; j++)D[i][j][0] = 1;
	for (i = 1; i <= n; i++)for (j = 1; j <= m; j++) for (p = 1; p <= k; p++) {
		D[i][j][p] = ((D[i][j - 1][p] + D[i-1][j][p])%mod - D[i-1][j-1][p]+mod)%mod;
		if (a[i] > b[j])D[i][j][p] = (D[i][j][p] + D[i - 1][j - 1][p - 1]) % mod;
	}
	printf("%lld", D[n][m][k]);
	return 0;
}

I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgYVsxMjEyXSwgYlsxMjEyXTsKbG9uZyBsb25nIERbMTIxMl1bMTIxMl1bMTFdOwpsb25nIGxvbmcgbW9kID0gMWU5ICsgOTsKaW50IG1haW4oKSB7CglpbnQgbiwgbSwgaywgaSwgaiwgcDsKCXNjYW5mKCIlZCVkJWQiLCAmbiwgJm0sICZrKTsKCWZvciAoaSA9IDE7IGkgPD0gbjsgaSsrKXNjYW5mKCIlZCIsICZhW2ldKTsKCWZvciAoaSA9IDE7IGkgPD0gbTsgaSsrKXNjYW5mKCIlZCIsICZiW2ldKTsKCXNvcnQoYSArIDEsIGEgKyAxICsgbik7IHNvcnQoYiArIDEsIGIgKyBtICsgMSk7Cglmb3IgKGkgPSAwOyBpIDw9IG47IGkrKylmb3IgKGogPSAwOyBqIDw9IG07IGorKylEW2ldW2pdWzBdID0gMTsKCWZvciAoaSA9IDE7IGkgPD0gbjsgaSsrKWZvciAoaiA9IDE7IGogPD0gbTsgaisrKSBmb3IgKHAgPSAxOyBwIDw9IGs7IHArKykgewoJCURbaV1bal1bcF0gPSAoKERbaV1baiAtIDFdW3BdICsgRFtpLTFdW2pdW3BdKSVtb2QgLSBEW2ktMV1bai0xXVtwXSttb2QpJW1vZDsKCQlpZiAoYVtpXSA+IGJbal0pRFtpXVtqXVtwXSA9IChEW2ldW2pdW3BdICsgRFtpIC0gMV1baiAtIDFdW3AgLSAxXSkgJSBtb2Q7Cgl9CglwcmludGYoIiVsbGQiLCBEW25dW21dW2tdKTsKCXJldHVybiAwOwp9

MTAgMTAgMwoxIDIgMiA2IDYgNyA4IDkgMTQgMTcKMSAzIDggMTAgMTAgMTYgMTYgMTggMTkgMTk=

10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19