题目描述

Every year, Farmer John brings his $N$ cows to compete for "best in show" at the state fair. His arch-rival, Farmer Paul, brings his $M$ cows to compete as well ($1 \leq N \leq 1000, 1 \leq M \leq 1000$).

Each of the $N + M$ cows at the event receive an individual integer score. However, the final competition this year will be determined based on teams of $K$ cows ($1 \leq K \leq 10$), as follows: Farmer John and Farmer Paul both select teams of $K$ of their respective cows to compete. The cows on these two teams are then paired off: the highest-scoring cow on FJ's team is paired with the highest-scoring cow on FP's team, the second-highest-scoring cow on FJ's team is paired with the second-highest-scoring cow on FP's team, and so on. FJ wins if in each of these pairs, his cow has the higher score.

Please help FJ count the number of different ways he and FP can choose their teams such that FJ will win the contest. That is, each distinct pair (set of $K$ cows for FJ, set of $K$ cows for FP) where FJ wins should be counted. Print your answer modulo 1,000,000,009.

输入格式

The first line of input contains $N$, $M$, and $K$. The value of $K$ will be no larger than $N$ or $M$.

The next line contains the $N$ scores of FJ's cows.

The final line contains the $M$ scores of FP's cows.

输出格式

Print the number of ways FJ and FP can pick teams such that FJ wins, modulo 1,000,000,009.

题目大意

每年，Farmer John 都要带领他的 $N$ 头奶牛参加才艺比赛，他的对手 Farmer Paul，会带着 $M$ 头奶牛参加比赛。

所有 $N+M$ 头奶牛都会得到评委给出的一个分数。而比赛的最终结果将取决于 $K$ 头奶牛组成的队伍。更具体地来说，FJ 和 FP 各自从自己的奶牛中挑选 $K$ 头奶牛组队，FJ 队伍中分数最高的奶牛将和 FP 队伍中分数最高的奶牛进行比较，FJ 队伍中分数次高的奶牛将和 FP 队伍中分数次高的奶牛进行比较，以此类推。如果 FJ 队伍中的每头奶牛的分数都比相对应的对手的分数高的话，FJ 就获得了胜利。

现在请你求出，在所有的组队情况中，有多少种情况 FJ 能取得胜利，输出方案数对 $1\,000\,000\,009$ 取模的结果。

数据范围：$1\leq N,M \leq 1000$,$1 \leq K \leq 10$。

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

382