Побудова команди#10566
Щороку фермер Джон привозить своїх корів на змагання за звання «найкращої корови» на державному ярмарку. Його заклятий суперник, фермер Пол, також привозить своїх корів для участі у змаганні.
Кожна з n + m корів отримує індивідуальну цілочислову оцінку. Однак цього року підсумок змагання визначатиметься командами з корів наступним чином: фермер Джон і фермер Пол обирають по команді з своїх корів. Потім корови з двох команд розбиваються на пари відповідно до їхніх оцінок: корова з найбільшою оцінкою в команді FJ змагається з коровою з найбільшою оцінкою в команді FP, корови з другими за величиною оцінками утворюють наступну пару і так далі. FJ переможе, якщо в кожній парі його корова має оцінку строго вищу, ніж відповідна корова команди FP.
Допоможіть FJ підрахувати кількість різних способів, якими він та FP можуть обрати свої команди так, щоб FJ виграв змагання. Іншими словами, необхідно посахувати кожну різну пару, що складається з множини з корів, обраних FJ, і множини з корів, обраних FP, якщо FJ виграє. Виведіть відповідь за модулем 10^9 + 9.
У першому рядку знаходяться три цілих числа та k~(1 \le n, m \le 1000, 1 \le k \le 10). Значення не перевищує ні , ні . У наступному рядку містяться оцінок корів FJ.
У останньому рядку містяться оцінок корів FP.
Виведіть кількість способів, якими FJ та FP можуть обрати свої команди так, щоб FJ переміг, за модулем 10^9 + 9.
Приклад 1