Побудова команди
Кожного року фермер Джон привозить 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.