Pewna osoba grająca w szczytowe osiągnięcie gier mobilnych pewnego dnia bardzo się złości na grę, w którą musi grać podczas próby podpisania kontraktu. Gra przebiega następująco:
- Pula kart składa się z liczb od $1$ do $2N+K$.
- Gra losuje z tej puli kolejno $N$ kart (bez zwracania, czyli żadna liczba nie może zostać wylosowana dwukrotnie).
- Po wylosowanych kartach gracz zgaduje, czy następna karta będzie większa, czy mniejsza.
Gracza złości to, że wskutek pecha po małej liczbie stale pojawia się jeszcze mniejsza, a po dużej — jeszcze większa. Postanawia temu zapobiec, zmieniając mechanizm losowości gry. Jego zmiana dodaje do losowania kart dwie reguły:
- Jeśli wylosowano kartę z liczbą od $1$ do $N$, liczba na następnej wylosowanej karcie musi być ściśle większa od $N$ ($>N$).
- Jeśli wylosowano kartę z liczbą od $N+K+1$ do $2N+K$, liczba na następnej wylosowanej karcie musi być ściśle mniejsza od $N+K+1$ ($<N+K+1$).
Gracz zastanawia się, jak bardzo popsuł grę tymi zmianami. Miarą tego jest stosunek liczby wszystkich możliwych różnych ciągów wylosowanych kart w zmodyfikowanej wersji gry do liczby wszystkich możliwych ciągów wylosowanych kart w zwykłej wersji. Prosi Cię o podanie tego stosunku modulo $10^9+7$.
Szczegóły implementacji
Należy zaimplementować następującą funkcję:
int oyun(int N, int K)- $N$ i $K$ to liczby całkowite określające pulę kart i liczbę losowanych kart zgodnie z opisem zadania.
- Funkcja powinna zwrócić żądany stosunek.
- Funkcja zostanie wywołana dokładnie raz w każdym teście.
Ograniczenia
- $1\le N\le 10^6$.
- $1\le K\le 100$.
Podzadania
| Podzadanie | Punkty | Dodatkowe ograniczenia | Zależności |
|---|---|---|---|
| 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 | Brak dodatkowych ograniczeń | 1, 2, 3, 4 |
Przykład
oyun(2, 1)
Powyższe wywołanie funkcji powinno zwrócić 600000005.
Nasze liczby to $1,2,3,4,5$. Losujemy 2 karty. W zwykłej sytuacji można je wylosować na 20 różnych sposobów. W zmodyfikowanej grze, jeśli pierwsza karta to $1$, $2$, $4$ lub $5$, istnieją 3 różne możliwości wyboru drugiej karty; jeśli pierwsza karta to $3$, istnieją 4 możliwości. Łącznie w zmodyfikowanej grze jest więc 16 możliwości. $\frac{16}{20}=\frac45$. To prawdopodobieństwo odpowiada wartości $600000005$ przy przyjętym module.
Przykładowy program oceniający
Przykładowy program oceniający oczekuje każdego przypadku w następującym formacie:
$$N\ K$$
Jeżeli wymagana funkcja pomyślnie zwróci liczbę całkowitą, program wypisze ten wynik $R$ w następującym formacie:
$$R$$