Однажды любитель лучших мобильных игр сильно разозлился на игру, в которую ему пришлось играть при попытке подписать договор. Игра устроена следующим образом:
- Имеется набор карт с числами от $1$ до $2N+K$.
- Игра по одной вытягивает $N$ карт из этого набора (без возвращения, то есть одно число не может быть вытянуто дважды).
- После вытягивания карт игрок угадывает, будет ли число на следующей карте больше или меньше.
Игрока злит то, что из-за невезения за маленьким числом постоянно следует ещё меньшее, а за большим — ещё большее. Он решает предотвратить это, изменив механизм случайного выбора в игре. Его изменение добавляет к вытягиванию карт два правила:
- Если вытянута карта с числом от $1$ до $N$, число на следующей карте должно быть строго больше $N$ ($>N$).
- Если вытянута карта с числом от $N+K+1$ до $2N+K$, число на следующей карте должно быть строго меньше $N+K+1$ ($<N+K+1$).
После этих изменений игрок хочет узнать, насколько он сломал игру. Мерой этого является отношение числа всех возможных различных последовательностей вытягивания карт в изменённой игре к числу всех возможных последовательностей в обычной игре. Он просит вас найти это отношение по модулю $10^9+7$.
Детали реализации
Вам необходимо реализовать следующую функцию:
int oyun(int N, int K)- $N$ и $K$ — целые числа, задающие набор карт и число вытягиваемых карт, как описано в условии.
- Функция должна вернуть требуемое отношение.
- В каждом тесте функция будет вызвана ровно один раз.
Ограничения
- $1\le N\le 10^6$
- $1\le K\le 100$
Подзадачи
| Подзадача | Баллы | Дополнительные ограничения | Зависимости |
|---|---|---|---|
| 1 | 10 | $1\le N,K\le 6$ | — |
| 2 | 18 | $1\le N\le 100$ | 1 |
| 3 | 6 | $1\le N\le 1000$ | 1, 2 |
| 4 | 47 | $1\le N\le 10^4$ | 1, 2, 3 |
| 5 | 19 | Нет дополнительных ограничений | 1, 2, 3, 4 |
Примеры
oyun(2, 1)
Этот вызов должен вернуть $600000005$.
Имеются числа $1,2,3,4,5$. Нужно вытянуть 2 карты. В обычной игре это можно сделать 20 различными способами. В изменённой игре, если первая карта равна $1$, $2$, $4$ или $5$, для второй карты есть 3 различных варианта; если первая карта равна $3$, для второй есть 4 варианта. Всего в изменённой игре получается 16 вариантов. $\frac{16}{20}=\frac45$. По используемому модулю эта вероятность равна $600000005$.
Пример проверяющей программы
Пример проверяющей программы ожидает каждый тест в следующем формате:
$$N\ K$$
Если реализованная функция успешно возвращает целое число, программа выведет этот результат $R$ в следующем формате:
$$R$$