2576. [USACO Dec16]团队建设

【题目描述】

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

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

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

【输入格式】

第一行三个整数N,M,K。

第二行N个整数，表示Farmer John的牛的得分。

第三行M个整数，表示Farmer Paul的牛的得分。

【输出格式】

一行一个整数，表示Farmer John能取得胜利的方案数，方案数对1000000009 取模。

【样例输入】

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

【样例输出】

382

【数据范围与约定】

1≤N,M≤1000,1≤K≤10。