A7079 | 奶牛比赛

每年，Welcome24ever 都会带着他的 $N$ 头奶牛参加州展览会的“最佳展示”比赛。他的劲敌 fangz 也会带着他的 $M$ 头奶牛参加比赛（$1 \leq N \leq 1000, 1 \leq M \leq 1000$）。

参加比赛的 $N + M$ 头奶牛每头都会获得一个单独的整数得分。今年的最终比赛将由 $K$ 头奶牛组成的团队决定（$1 \leq K \leq 10$），规则如下：

Welcome24ever 和 fangz 各自选择 $K$ 头奶牛组成团队进行比赛。这两个团队的奶牛会在各自团队内部按得分从小到大排序，然后按名次一一配对：

- Welcome24ever 团队中得分第 $1$ 小的奶牛，与 fangz 团队中得分第 $1$ 小的奶牛配对；
- Welcome24ever 团队中得分第 $2$ 小的奶牛，与 fangz 团队中得分第 $2$ 小的奶牛配对；
- 以此类推，直到第 $K$ 头奶牛。

如果在这 $K$ 对配对中，每一对中 Welcome24ever 的奶牛得分都严格高于 fangz 的那头奶牛（即对于所有 $1 \leq i \leq K$，都有 $a_i > b_i$），那么 Welcome24ever 获胜。

请你帮助 Welcome24ever 计算：他和 fangz 可以选择团队的**不同方式**的数量，使得 Welcome24ever 能够获胜。也就是说，每一种不同的有序二元组

- （Welcome24ever 选出的 $K$ 头奶牛集合，
- fangz 选出的 $K$ 头奶牛集合），

只要在上述规则下 Welcome24ever 获胜，就计入答案。由于答案可能很大，请输出对 $1\,000\,000\,009$ 取模的结果。

第一行包含三个整数 $N$、$M$ 和 $K$。保证 $1 \leq N,M \leq 1000$，$1 \leq K \leq 10$，且 $K$ 不会超过 $N$ 或 $M$。

第二行包含 $N$ 个整数，表示 Welcome24ever 的 $N$ 头奶牛的得分。

第三行包含 $M$ 个整数，表示 fangz 的 $M$ 头奶牛的得分。

输出一个整数，表示选择团队的方案数，对 $1\,000\,000\,009$ 取模。