题目描述：

篮球教练甲和教练乙分别从各自球队中挑选 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

提示