Каждый год, Фермер Джон привозит \(N\) своих коров соревноваться на ярмарку.
Его главный соперник Фермер Пауль привозит своих \(M\) коров
(\(1 \leq N \leq 1000, 1 \leq M \leq 1000\)).
Каждая из этих \(N + M\) коров получает индивидуальную оценку. Однако
в текущем году финальное соревнование будет ограничено командой из \(K\) коров
(\(1 \leq K \leq 10\)). Поэтому ФД и ФП отбирают по \(K\) коров. Затем они
разбиваются на пары: лучшая корова ФД становится в пару с лучшей коровой ФП,
вторая корова ФД, становится в пару со второй коровой ФП и т.д.
ФД выиграет, если в каждой из этих пар его корова будет иметь более высокую
оценку.
Помогите ФД посчитать количество различных способов которыми ФД и ФП могут
отобрать своих коров так, чтобы ФД выиграл в соревновании. Точнее, каждая
считается каждая различная пара (\(K\) коров от ФД, и \(K\) коров от ФП).
Выведите ответ по модулю 1,000,000,009.
ФОРМАТ ВВОДА (файл team.in):
Первая строка ввода содержит
\(N\),
\(M\),
\(K\). Значение
\(K\) будет не более
чем
\(N\) и
\(M\).
Следующая строка содержит оценки \(N\) коров ФД.
Следующая строка содержит оценки \(M\) коров ФП.
ФОРМАТ ВЫВОДА (файл team.out):
Выведите количеаство способов, которыми ФД и ФП могут отобрать свои команды,
чтобы победил ФД. Выводите это число по модулю 1,000,000,009.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19
|
382
|