Every year, Farmer John brings his NN cows to compete for “best in show” at the state fair. His arch
-rival, Farmer Paul, brings his MM cows to compete as well (1≤N≤1000,1≤M≤1000).Each of the N+MN+
M cows at the event receive an individual integer score. However, the final competition this year wi
ll be determined based on teams of KK cows (1≤K≤10), as follows: Farmer John and Farmer Paul both
select teams of KK 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 s
econd-highest-scoring cow on FJ’s team is paired with the second-highest-scoring cow on FP’s team, a
nd so on. FJ wins if in each of these pairs, his cow has the higher score.Please help FJ count the n
umber of different ways he and FP can choose their teams such that FJ will win the contest. That is,
 each distinct pair (set of KK cows for FJ, set of KK cows for FP) where FJ wins should be counted.
Print your answer modulo 1,000,000,009.
(1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)。每只牛都有自己的分数。两人会选择K只牛组成队伍(1 ≤ K ≤ 10),两队
约翰计算约翰打败保罗的方案数 mod 1000000009。两种方案不同,当且仅当约翰或保罗选择的牛的集合与另一种


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.

Sample Input

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

Sample Output




Platinum 鸣谢Firstlast提供译文

设dp[i][j]k]前i头fj的牛 j头fp的牛 配对k次的方案数


dp[i][j+1][k]->dp[i+1][j+1][k]会算重复 所以减去即可


分类: 动态规划


辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330