P2098 [USACO16DEC] Team Building P

每年，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$ 取模。

无

无