Costruzione della squadra

Ogni anno il fattore John porta le sue $n$ mucche alla competizione per il titolo di "mucca migliore" alla fiera statale. Il suo acerrimo rivale, il fattore Paul, porta anche le sue $m$ mucche per partecipare alla competizione.

Ciascuna delle n + m mucche riceve un punteggio intero individuale. Tuttavia, quest'anno il risultato della competizione sarà determinato da squadre di $k$ mucche nel modo seguente: il fattore John e il fattore Paul scelgono ciascuno una squadra di $k$ delle proprie mucche. Poi le mucche delle due squadre vengono accoppiate in base ai loro punteggi: la mucca con il punteggio più alto nella squadra di FJ affronta la mucca con il punteggio più alto nella squadra di FP, le mucche con i secondi punteggi più alti formano la coppia successiva, e così via. FJ vince se in ogni coppia la sua mucca ha un punteggio strettamente superiore a quello della mucca corrispondente nella squadra di FP.

Aiuta FJ a contare il numero di modi diversi in cui lui e FP possono scegliere le proprie squadre in modo che FJ vinca la competizione. In altre parole, è necessario contare ogni coppia distinta formata da un insieme di $k$ mucche scelte da FJ e un insieme di $k$ mucche scelte da FP, tale che FJ vinca. Restituisci la risposta modulo 10^9 + 9.