Una persona che gioca al massimo dei giochi per dispositivi mobili si arrabbia molto con il gioco a cui deve giocare mentre cerca un giorno di firmare un contratto. Il gioco si svolge così:
- Esiste un insieme di carte con numeri da $1$ a $2N+K$.
- Il gioco estrae $N$ carte una alla volta da questo insieme (senza reinserimento, cioè uno stesso numero non può essere estratto due volte).
- Dopo le carte estratte, il giocatore cerca di indovinare se la carta successiva sarà maggiore o minore.
Ciò che fa arrabbiare il giocatore è che, a causa della sua sfortuna, dopo un numero piccolo arriva continuamente un numero ancora più piccolo, e dopo un numero grande arriva continuamente un numero ancora più grande. Il giocatore cerca quindi di impedirlo modificando il meccanismo di casualità del gioco. La sua modifica aggiunge le seguenti due regole all'estrazione delle carte:
- Se viene estratta una carta con un numero da $1$ a $N$, il numero della carta estratta successivamente deve essere strettamente maggiore di $N$ ($>N$).
- Se viene estratta una carta con un numero da $N+K+1$ a $2N+K$, il numero della carta estratta successivamente deve essere strettamente minore di $N+K+1$ ($<N+K+1$).
Dopo queste modifiche, il giocatore si chiede quanto abbia alterato il gioco. La misura di questa alterazione è il rapporto tra il numero di tutte le diverse sequenze possibili di estrazione delle carte nella versione modificata del gioco e il numero di tutte le sequenze possibili nella versione normale. Ti chiede questo rapporto modulo $10^9+7$.
Dettagli di implementazione
Devi implementare la seguente funzione:
int oyun(int N, int K)- $N$ e $K$ sono interi che determinano l'insieme delle carte e il numero di carte da estrarre, come indicato nel problema.
- Questa funzione deve restituire il rapporto richiesto.
- Questa funzione verrà chiamata esattamente una volta in ciascun test.
Vincoli
- $1\le N\le 10^6$.
- $1\le K\le 100$.
Sottoproblemi e punteggio
| Sottoproblema | Punti | Vincoli aggiuntivi | Dipendenze |
|---|---|---|---|
| 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 | Nessun vincolo aggiuntivo | 1, 2, 3, 4 |
Esempi
oyun(2, 1)
La chiamata alla funzione sopra deve restituire $600000005$.
I nostri numeri sono $1,2,3,4,5$. Estrarremo 2 carte. Nella situazione normale, possiamo estrarre le carte in 20 modi diversi. Nel gioco modificato, se la prima carta è $1$, $2$, $4$ o $5$, ci sono 3 possibilità diverse per la seconda carta; se è $3$, ci sono 4 possibilità diverse. Quindi il gioco modificato ha in totale 16 possibilità. $\frac{16}{20}=\frac45$. Questa probabilità equivale a $600000005$ con il nostro modulo.
Grader di esempio
Il grader di esempio si aspetta ciascun caso nel seguente formato:
$$N\ K$$
Se la funzione richiesta restituisce correttamente un intero, stamperà questo risultato $R$ nel seguente formato:
$$R$$