Jemand, der die Spitze der Handyspiele spielt, ärgert sich eines Tages sehr über das Spiel, das er spielen muss, während er versucht, einen Vertrag zu unterschreiben. Das Spiel läuft wie folgt ab:
- Es gibt einen Kartenvorrat mit den Zahlen von $1$ bis $2N+K$.
- Das Spiel zieht nacheinander $N$ Karten aus diesem Vorrat (ohne Zurücklegen, das heißt, eine Zahl kann nicht zweimal gezogen werden).
- Nach den gezogenen Karten rät der Spieler, ob die nächste Karte höher oder niedriger sein wird.
Was den Spieler ärgert, ist, dass wegen seines Pechs auf eine kleine Zahl ständig eine kleinere und auf eine große Zahl ständig eine größere folgt. Daher möchte der Spieler dies verhindern, indem er den Zufallsmechanismus des Spiels verändert. Seine Änderung fügt dem Ziehen der Karten die folgenden zwei Regeln hinzu:
- Wird eine Karte mit einer Zahl von $1$ bis $N$ gezogen, muss die Zahl auf der nächsten gezogenen Karte strikt größer als $N$ sein ($>N$).
- Wird eine Karte mit einer Zahl von $N+K+1$ bis $2N+K$ gezogen, muss die Zahl auf der nächsten gezogenen Karte strikt kleiner als $N+K+1$ sein ($<N+K+1$).
Der Spieler fragt sich, wie sehr er das Spiel durch diese Änderungen kaputtgemacht hat. Als Maß dafür dient das Verhältnis der Anzahl aller möglichen verschiedenen Kartenfolgen in der veränderten Version des Spiels zur Anzahl aller möglichen Kartenfolgen in der normalen Version. Er bittet dich um dieses Verhältnis modulo $10^9+7$.
Implementierungsdetails
Du sollst die folgende Funktion implementieren:
int oyun(int N, int K)- $N$ und $K$ sind ganze Zahlen, die wie in der Aufgabenstellung beschrieben den Kartenvorrat und die Anzahl der zu ziehenden Karten bestimmen.
- Diese Funktion soll das gesuchte Verhältnis zurückgeben.
- Diese Funktion wird in jedem Test genau einmal aufgerufen.
Beschränkungen
- $1\le N\le10^6$
- $1\le K\le100$
Teilaufgaben
| Teilaufgabe | Punkte | Zusätzliche Beschränkungen | Abhängigkeiten |
|---|---|---|---|
| 1 | 10 | $1\le N,K\le6$ | — |
| 2 | 18 | $1\le N\le100$ | 1 |
| 3 | 6 | $1\le N\le1000$ | 1, 2 |
| 4 | 47 | $1\le N\le10^4$ | 1, 2, 3 |
| 5 | 19 | Keine zusätzlichen Beschränkungen | 1, 2, 3, 4 |
Beispiele
oyun(2, 1)
Der obige Funktionsaufruf soll $600000005$ zurückgeben.
Unsere Zahlen sind $1,2,3,4,5$. Wir ziehen $2$ Karten. Normalerweise können wir die Karten auf $20$ verschiedene Arten ziehen. Im veränderten Spiel gibt es, wenn unsere erste Karte $1$, $2$, $4$ oder $5$ ist, $3$ verschiedene Möglichkeiten für die zweite Karte; ist sie $3$, gibt es $4$ verschiedene Möglichkeiten für die zweite Karte. Damit gibt es im veränderten Spiel insgesamt $16$ Möglichkeiten. $\frac{16}{20}=\frac45$. Diese Wahrscheinlichkeit entspricht modulo unserem Modulus dem Wert $600000005$.
Beispiel-Grader
Der Beispiel-Grader erwartet jeden Fall im folgenden Format:
$$N\ K$$
Wenn die geforderte Funktion erfolgreich eine ganze Zahl zurückgibt, gibt er dieses Ergebnis $R$ im folgenden Format aus:
$$R$$