Winning Team Selections

Farmer John and Farmer Paul are competing at the state fair with their respective cows. Farmer John has N cows and Farmer Paul has M cows. Each cow receives an individual integer score. This year, the competition is decided based on teams consisting of K cows. Both farmers must select K cows from their herds. The teams are then sorted by score and paired off: the highest scoring cow of Farmer John's team is paired with the highest scoring cow of Farmer Paul's team, the second highest with the second highest, and so on. Farmer John wins if in every one of these pairs, his cow's score is strictly greater than that of Farmer Paul's cow.

Your task is to count the number of different ways the two farmers can choose their teams such that Farmer John wins. Two ways are considered different if the set of cows chosen by either farmer differ. Since the answer can be large, output it modulo \(10^9+9\).

Note: The cows in each team are paired after sorting by their scores in increasing order. Thus, if we denote Farmer John's chosen team by \(F = \{f_1, f_2, \ldots, f_K\}\) and Farmer Paul's chosen team by \(P = \{p_1, p_2, \ldots, p_K\}\) where \(f_1 < f_2 < \cdots < f_K\) and \(p_1 < p_2 < \cdots < p_K\), then the winning condition is:

[ f_i > p_i, \quad \text{for all } i = 1, 2, \ldots, K. ]

inputFormat

The first line contains three integers \(N, M, K\) where \(1 \leq N, M \leq 1000\) and \(1 \leq K \leq 10\).

The second line contains \(N\) integers representing the scores of Farmer John's cows.

The third line contains \(M\) integers representing the scores of Farmer Paul's cows.

outputFormat

Output the number of ways the teams can be chosen such that Farmer John wins, modulo \(10^9+9\).

sample

3 3 1
5 7 9
4 8 10

4