팀 짜기

해마다 농부 존은 소 $N$마리를 데리고 주 박람회의 최우수 품평회에 나간다. 경쟁자인 농부 폴도 자기 소 $M$마리를 데리고 나온다. ($1 \le N \le 1000$, $1 \le M \le 1000$)

박람회에 나온 소 $N+M$마리는 각각 정수 점수를 받는다. 올해 최종 승부는 소 $K$마리로 이루어진 팀으로 가린다. ($1 \le K \le 10$) 존과 폴은 각자 자기 소 중에서 $K$마리를 골라 팀을 짠다. 두 팀은 점수 순위대로 짝을 짓는다. 존의 팀에서 점수가 가장 높은 소는 폴의 팀에서 점수가 가장 높은 소와 짝이 되고, 두 번째로 높은 소는 두 번째로 높은 소와 짝이 되며, 나머지 짝도 같은 방식으로 정해진다. $K$개의 짝 모두에서 존의 소 점수가 폴의 소 점수보다 크면 존이 이긴다.

존이 이기는 팀 조합의 수를 구한다. 존이 고른 $K$마리 집합과 폴이 고른 $K$마리 집합의 순서쌍을 하나의 조합으로 보고, 두 집합 중 어느 한쪽이라도 다르면 서로 다른 조합이다. 답을 $1000000009$로 나눈 나머지를 출력한다.

첫째 줄에 $N$, $M$, $K$가 주어진다. $K$는 $N$보다 크지 않고 $M$보다도 크지 않다.

둘째 줄에 존의 소 $N$마리의 점수가 주어진다.

셋째 줄에 폴의 소 $M$마리의 점수가 주어진다.

모든 점수는 $1$ 이상 $100000$ 이하의 정수다.

존이 이기는 팀 조합의 수를 $1000000009$로 나눈 나머지를 한 줄에 출력한다.