Team Building

Every year Farmer John brings his $N$ cows to the state fair to compete for best in show. His rival Farmer Paul brings his own $M$ cows. ($1 \le N \le 1000$, $1 \le M \le 1000$)

Each of the $N+M$ cows at the fair receives an integer score. This year the final contest is decided by teams of $K$ cows. ($1 \le K \le 10$) John and Paul each pick $K$ of their own cows to form a team. The two teams are then paired off by score rank: the highest scoring cow on John's team is paired with the highest scoring cow on Paul's team, the second highest with the second highest, and the remaining pairs follow the same rule. John wins when his cow has the strictly higher score in every one of the $K$ pairs.

Count the team choices for which John wins. A choice is the pair of John's set of $K$ cows and Paul's set of $K$ cows, and two choices differ when either of the two sets differs. Print the count modulo $1000000009$.

The first line contains $N$, $M$, and $K$. The value of $K$ is no larger than $N$ and no larger than $M$.

The second line contains the scores of John's $N$ cows.

The third line contains the scores of Paul's $M$ cows.

Every score is an integer between $1$ and $100000$.

Print on one line the number of team choices for which John wins, modulo $1000000009$.