### 问题描述 每年，小齐都会带着他的 $N$ 头奶牛参加州际农业大赛，争夺“最佳展示”奖项。然而，他的宿敌小保也会带着他的 $M$ 头奶牛参赛。 在比赛中，每头奶牛都会获得一个独立的整数评分。今年的决赛将根据大小为 $K$ 的奶牛团队（$1 \leq K \leq 10$）来决定比赛结果。小齐和小保都会选择各自的 $K$ 头奶牛组成团队参赛。然后，这两个团队的奶牛会被配对：小齐团队中评分最高的奶牛将与小保团队中评分最高的奶牛配对，第二高的奶牛也是如此，以此类推。小齐只有在每对配对中，他的奶牛都获得了更高的分数时才能赢得比赛。 请帮助小齐计算选择团队的不同方式，使得小齐能够获胜。也就是说，要计算每种不同的选择方式，其中小齐都能够在比赛中获胜。请将答案输出模 $1,000,000,009$。 ### 输入格式 第一行输入 $N$、$M$ 和 $K$，表示小齐和小保各自的奶牛数量，以及奶牛团队的大小。 第二行输入小齐奶牛的评分。 第三行输入小保奶牛的评分。 ### 输出格式 输出小齐和小保可以选择奶牛团队的方式数量，取模 $1,000,000,009$。 ### 样例输入 ``` 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 \leq N \leq 1000，1 \leq M \leq 1000$。