Битва подписчиков
ограничение по времени на тест: 1 секунда ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод вывод: стандартный вывод
Среди стримеров набирает популярность новый формат интерактива битва подписчиков. Его суть такова: два стримера, назовем их А и В, выбирают по К своих подписчиков к себе в команду. Затем между этими командами играются к матчей в формате 1 х 1.
Каждый игрок имеет свой рейтинг в виде целого числа. Результат матча целиком зависит от рейтинга игроков: игрок с большим рейтингом всегда выигрывает игрока с меньшим. Если рейтинги игроков равны, то матч заканчивается ничьей.
Для того, чтобы матчи были более зрелищными игроки внутри команд сортируются по рейтингу, а затем каждый из игроков играет один матч с игроком другой команды на той же позиции по рейтингу внутри команды. Так самый сильный игрок команды А играет с самым сильным игроком в команде В, второй по рейтингу игрок в команде А играет с вторым по рейтингу в команде В и т. д.
Вам стало интересно сколько существует способов выбрать команды для стримеров А и В так, чтобы команда А одержала разгромную победу и выиграла все К матчей. Вам известны количество подписчиков каждого из стримеров, а также рейтинг каждого их них. Вычислите количество способов составить команды описанным образом по модулю 109 + 9.
Два способа считаются различными, если существует хотябы один подписчик (у А или у В), который в одном способе был взят в команду своего стримера, а в другом - не был.
Вы можете считать, что ни один из подписчиков стримера А не подписан на стримера В и наоборот.
Входные данные
В первой строке задается три целых числа N, М и К (1 ≤ N ≤ 1000; 1 ≤ M < 1000; 1 <K< 10; K < N; K ≤ М) - количество подписчиков стримера А, количество подписчиков стримера В и размер команды для битвы подписчиков.
Во второй строке задается N целых чисел а1, 02, ..., ам (1 ≤ ; < 105), где а; — это рейтинг 1-го подписчика стримера А.
-
В третьей строке задается М целых чисел 61, 62,..., вм (1; 105), где b; — это рейтинг 1-го подписчика стримера В. Рейтинги подписков заданы в порядке неубывания. (a; < di+1; b; < bi+1)
Выходные данные
Выведите одно целое число - количество способов составить команды так, чтобы команда А выиграла все матчи, по модулю 109 + 9. (Выведите остаток от деления этого числа на 109 + 9)
Пример
входные данные
10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19
выходные данные
382
ограничение по времени на тест: 1 секунда ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод вывод: стандартный вывод
Среди стримеров набирает популярность новый формат интерактива битва подписчиков. Его суть такова: два стримера, назовем их А и В, выбирают по К своих подписчиков к себе в команду. Затем между этими командами играются к матчей в формате 1 х 1.
Каждый игрок имеет свой рейтинг в виде целого числа. Результат матча целиком зависит от рейтинга игроков: игрок с большим рейтингом всегда выигрывает игрока с меньшим. Если рейтинги игроков равны, то матч заканчивается ничьей.
Для того, чтобы матчи были более зрелищными игроки внутри команд сортируются по рейтингу, а затем каждый из игроков играет один матч с игроком другой команды на той же позиции по рейтингу внутри команды. Так самый сильный игрок команды А играет с самым сильным игроком в команде В, второй по рейтингу игрок в команде А играет с вторым по рейтингу в команде В и т. д.
Вам стало интересно сколько существует способов выбрать команды для стримеров А и В так, чтобы команда А одержала разгромную победу и выиграла все К матчей. Вам известны количество подписчиков каждого из стримеров, а также рейтинг каждого их них. Вычислите количество способов составить команды описанным образом по модулю 109 + 9.
Два способа считаются различными, если существует хотябы один подписчик (у А или у В), который в одном способе был взят в команду своего стримера, а в другом - не был.
Вы можете считать, что ни один из подписчиков стримера А не подписан на стримера В и наоборот.
Входные данные
В первой строке задается три целых числа N, М и К (1 ≤ N ≤ 1000; 1 ≤ M < 1000; 1 <K< 10; K < N; K ≤ М) - количество подписчиков стримера А, количество подписчиков стримера В и размер команды для битвы подписчиков.
Во второй строке задается N целых чисел а1, 02, ..., ам (1 ≤ ; < 105), где а; — это рейтинг 1-го подписчика стримера А.
-
В третьей строке задается М целых чисел 61, 62,..., вм (1; 105), где b; — это рейтинг 1-го подписчика стримера В. Рейтинги подписков заданы в порядке неубывания. (a; < di+1; b; < bi+1)
Выходные данные
Выведите одно целое число - количество способов составить команды так, чтобы команда А выиграла все матчи, по модулю 109 + 9. (Выведите остаток от деления этого числа на 109 + 9)
Пример
входные данные
10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19
выходные данные
382
