Имеется набор карточек для игры. На каждой карточке написано число, причём числа на разных карточках могут совпадать. В игру играют два человека. В каждом раунде игроки вытаскивают наугад по одной карточке и оставляют её у себя. У кого число на карточке оказалось больше, тот и победил в этом раунде. А если числа совпали, то в этом раунде объявляется ничья. Игра продолжается, пока не закончатся все карточки.
Нельзя заранее предсказать, сколько за время игры будет «ничьих» и побед у каждого игрока. Если на карточках были написаны числа $$$1,1,2,3,4,5$$$, то можно, например, сыграть $$$3$$$ таких раунда: $$$(2,5), (4,3), (1,1)$$$. В этом случае первый раунд выиграл второй игрок, второй раунд выиграл первый игрок, а третий раунд закончился «ничьей».
Спрашивается, а сколько существует разных интересных вариантов сыграть состоящую из $$$N$$$ раундов игру, если известны числа, написанные на карточках? Вариант считается интересным, если количество «ничьих» максимально для данного набора карточек, а также первый игрок выиграл ровно $$$K$$$ раз. Два варианта, отличающиеся только порядком раундов, считаются одинаковыми. Карточки, на которых записаны одинаковые числа, не отличаются друг от друга.
В первой строке на вход подается $$$N$$$ — количество раундов игры ($$$2 \le N \le 50\ 000$$$) и $$$K$$$ — количество побед первого игрока ($$$0 \le K \le N$$$).
Во второй строке записаны $$$2N$$$ натуральных чисел, не превосходящих $$$10^9$$$. Эти числа могут повторяться, они написаны на карточках.
На выходе должно быть записано количество различных вариантов сыграть $$$N$$$ игр так, чтобы количество «ничьих» было максимально возможным, а число побед первого игрока было равно $$$K$$$. Искомое число вариантов вычислить по модулю $$$10^9+7$$$. Порядок раундов в игре не важен. Важно лишь, карточки с какими числами участвовали в каждом раунде.
В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.
| Подзадача | Баллы | Дополнительные | Необходимые | Система |
| ограничения | подзадачи | оценки | ||
| $$$0$$$ | $$$0$$$ | Тесты из условия | — | — |
| $$$1$$$ | $$$14$$$ | $$$N \le 5$$$ | $$$0$$$ | полная |
| $$$2$$$ | $$$45$$$ | $$$N \le 1000$$$ | $$$0$$$, $$$1$$$ | полная |
| $$$3$$$ | $$$24$$$ | $$$K \le 100$$$ | $$$0$$$, $$$1$$$ | полная |
| $$$4$$$ | $$$17$$$ | — | $$$0$$$ – $$$3$$$ | полная |
3 24 6 4 5 2 4
3
2 24 6 4 5
0
Пояснения к первому примеру: нужно сыграть $$$3$$$ раунда. Максимальное количество «ничьих» при заданных числах на карточках равно $$$1$$$. Чтобы в двух оставшихся раундах выиграл первый игрок, возможны всего $$$3$$$ варианта сыграть эти три раунда: $$$[(6,5),(4,2),(4,4)]$$$, $$$[(6,4),(5,2),(4,4)]$$$, $$$[(6,2),(5,4),(4,4)]$$$.
Пояснения ко второму примеру: нужно сыграть $$$2$$$ раунда. Максимальное количество «ничьих» при заданных числах на карточках равно $$$1$$$, поэтому первый игрок не может выиграть два раза.
