Построение команды
Каждый год, Фермер Джон привозит n своих коров соревноваться на ярмарку. Его главный соперник Фермер Пауль привозит своих m коров.
Каждая из этих n + m коров получает индивидуальную оценку. Однако в текущем году финальное соревнование будет ограничено командой из k коров. Поэтому ФД и ФП отбирают по k коров. Затем они разбиваются на пары: лучшая корова ФД становится в пару с лучшей коровой ФП, вторая корова ФД, становится в пару со второй коровой ФП и т.д. ФД выиграет, если в каждой из этих пар его корова будет иметь более высокую оценку.
Помогите ФД посчитать количество различных способов которыми ФД и ФП могут отобрать своих коров так, чтобы ФД выиграл в соревновании. Точнее, каждая считается каждая различная пара (k коров от ФД, и k коров от ФП). Выведите ответ по модулю 10^9 + 9.
Входные данные
Первая строка содержит n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000), k (1 ≤ k ≤ 10). Значение k будет не более чем n и m. Следующая строка содержит оценки n коров ФД.
Следующая строка содержит оценки m коров ФП.
Выходные данные
Выведите количеаство способов, которыми ФД и ФП могут отобрать свои команды, чтобы победил ФД. Выводите это число по модулю 10^9 + 9.