Имеется набор карточек для игры. На каждой карточке написано число, причём числа на разных карточках могут совпадать. В игру играют два человека. В каждом раунде игроки вытаскивают наугад по одной карточке и оставляют её у себя. У кого число на карточке оказалось больше, тот и победил в этом раунде. А если числа совпали, то в этом раунде объявляется ничья. Игра продолжается, пока не закончатся все карточки.

Нельзя заранее предсказать, сколько за время игры будет «ничьих» и побед у каждого игрока. Если на карточках были написаны числа $$$1,1,2,3,4,5$$$, то можно, например, сыграть $$$3$$$ таких раунда: $$$(2,5), (4,3), (1,1)$$$. В этом случае первый раунд выиграл второй игрок, второй раунд выиграл первый игрок, а третий раунд закончился «ничьей».

Спрашивается, а сколько существует разных интересных вариантов сыграть состоящую из $$$N$$$ раундов игру, если известны числа, написанные на карточках? Вариант считается интересным, если количество «ничьих» максимально для данного набора карточек, а также первый игрок выиграл ровно $$$K$$$ раз. Два варианта, отличающиеся только порядком раундов, считаются одинаковыми. Карточки, на которых записаны одинаковые числа, не отличаются друг от друга.

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.