Every year, Farmer John brings his \(N\) cows to compete for "best in show" at the
state fair. His arch-rival, Farmer Paul, brings his \(M\) cows to compete as well
(\(1 \leq N \leq 1000, 1 \leq M \leq 1000\)).

Each of the \(N + M\) cows at the event receive an individual integer
score. However, the final competition this year will be determined
based on teams of \(K\) cows (\(1 \leq K \leq 10\)), as follows: Farmer
John and Farmer Paul both select teams of \(K\) of their respective cows
to compete. The cows on these two teams are then paired off: the
highest-scoring cow on FJ's team is paired with the highest-scoring
cow on FP's team, the second-highest-scoring cow on FJ's team is
paired with the second-highest-scoring cow on FP's team, and so on.
FJ wins if in each of these pairs, his cow has the higher score.

Please help FJ count the number of different ways he and FP can
choose their teams such that FJ will win the contest. That is, each
distinct pair (set of \(K\) cows for FJ, set of \(K\) cows for FP)
where FJ wins should be counted. Print your answer modulo
1,000,000,009.

Problem credits: Brian Dean and William Luo

Problem credits: Brian Dean and William Luo

The first line of input contains \(N\), \(M\), and \(K\). The value of \(K\) will be no
larger than \(N\) or \(M\).

The next line contains the \(N\) scores of FJ's cows.

The final line contains the \(M\) scores of FP's cows.

Print the number of ways FJ and FP can pick teams such that FJ wins, modulo
1,000,000,009.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Platinum