篮球全明星
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述：
篮球教练甲和教练乙分别从各自球队中挑选 K 名球员组成全明星阵容。甲队有 N 名球员，乙队有 M 名球员，所有球员的得分能力由 唯一整数表示。两队选出的 K 名球员将按得分从高到低排序后配对：甲队第 1 高分对乙队第 1 高分，第 2 高分对第 2 高分，依此 类推。若甲队每个位置的球员得分都高于乙队对应位置，则甲队获胜。 请计算甲队和乙队所有可能的选队组合中，满足甲队获胜条件的方案数，结果对 1000000009取模。
输入格式：
输入的第一行包含 N、M 和 K。K 的值不会超过 N 或 M。 第二行包含 教练甲 的 N 名球员的得分能力。 第三行包含 教练乙 的 M 名球员的得分能力。
输出格式：
输出 甲队获胜的方案数，结果对 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
