题目描述

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

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

Farmer John 和 Farmer Paul 各自选择 $K$ 头奶牛组成团队进行比赛。这两个团队的奶牛将按得分高低配对：

FJ 团队中得分最高的奶牛与 FP 团队中得分最高的奶牛配对，FJ 团队中得分第二高的奶牛与 FP 团队中得分第二高的奶牛配对，依此类推。如果在每一对中，FJ 的奶牛得分都更高，那么 FJ 获胜。

请帮助 FJ 计算他和 FP 可以选择团队的不同方式的数量，使得 FJ 能够赢得比赛。也就是说，每个不同的（FJ 的 $K$ 头奶牛集合，FP 的 $K$ 头奶牛集合）对，只要 FJ 获胜，都应被计入。输出结果对 $1\,000\,000\,009$ 取模。

输入格式

输入的第一行包含 $N$、$M$ 和 $K$。$K$ 的值不会超过 $N$ 或 $M$。

第二行包含 FJ 的 $N$ 头奶牛的得分。

第三行包含 FP 的 $M$ 头奶牛的得分。

输出格式

输出 FJ 和 FP 可以选择团队的方式数量，使得 FJ 获胜，结果对 $1\,000\,000\,009$ 取模。

输入输出样例 #1

输入 #1

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

输出 #1

382