문제

매년 우솔이는 $N$명의 팀원을, 민준이는 $M$명의 팀원을 데리고 알고리즘 대회에 참가한다. ($1 \le N \le 1\,000$; $1 \le M \le 1\,000$)

대회에 참여하는 $N + M$명의 팀원은 각각 정수 점수를 하나씩 받는다. 올해 최종 결선은 각 팀에서 $K$명씩 선발하여 구성한 팀 간의 대결로 진행된다. ($1 \le K \le 10$)

우솔이와 민준이는 각각 자신의 팀원 중 $K$명을 선택하여 최종 팀을 구성한다. 각 팀에서 선발된 팀원들은 다음과 같이 짝을 이룬다. 우솔이네 팀에서 가장 점수가 높은 팀원은 민준이네 팀에서 가장 점수가 높은 팀원과 짝이 되고, 두 번째로 점수가 높은 팀원은 상대 팀에서 두 번째로 점수가 높은 팀원과 짝이 되는 방식이다. 만약 모든 쌍에서 우솔이네 팀원의 점수가 민준이네 팀원의 점수보다 높다면 우솔이가 승리한다.

우솔이가 승리할 수 있도록 두 사람이 각자의 팀원을 선택하는 방법의 수를 구하는 프로그램을 작성하시오. 즉, 우솔이가 승리하는 모든 서로 다른 (우솔이네 팀원 $K$명의 집합, 민준이네 팀원 $K$명의 집합) 쌍의 개수를 구해야 한다. 출력값은 $1\,000\,000\,009$로 나눈 나머지여야 한다.

입력

첫째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $K$는 $N$과 $M$보다 크지 않다.

둘째 줄에 우솔이네 팀원 $N$명의 점수가 공백으로 구분되어 주어진다.

셋째 줄에 민준이네 팀원 $M$명의 점수가 공백으로 구분되어 주어진다.

출력

우솔이가 승리할 수 있는 팀 구성 방법의 수를 $1\,000\,000\,009$로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

382