Una persona que juega a lo mejor de los juegos para móviles se enfada mucho con el juego al que tiene que jugar un día mientras intenta firmar un contrato. El juego funciona de la siguiente manera:
- Hay un conjunto de cartas con los números del $1$ al $2N+K$.
- El juego extrae $N$ cartas de este conjunto, una a una y sin reposición; es decir, un número no puede extraerse dos veces.
- Tras las cartas extraídas, el jugador intenta adivinar si la siguiente carta será mayor o menor.
Lo que enfada al jugador es que, debido a su mala suerte, después de un número pequeño siempre aparece otro menor, y después de un número grande siempre aparece otro mayor. Por ello, el jugador intenta evitarlo modificando el mecanismo aleatorio del juego. Su modificación añade las dos reglas siguientes a la extracción de cartas:
- Si se extrae una carta con un número del $1$ al $N$, el número de la siguiente carta extraída debe ser estrictamente mayor que $N$ ($>N$).
- Si se extrae una carta con un número del $N+K+1$ al $2N+K$, el número de la siguiente carta extraída debe ser estrictamente menor que $N+K+1$ ($<N+K+1$).
El jugador se pregunta cuánto ha estropeado el juego con estas modificaciones. La medida de cuánto lo ha estropeado es la razón entre el número de todas las secuencias de extracción de cartas diferentes posibles en la versión modificada y el número de todas las secuencias posibles en la versión normal. Te pide esta razón módulo $10^9+7$.
Detalles de implementación
Debes implementar la función siguiente:
int oyun(int N, int K)- $N$ y $K$ son enteros que determinan el conjunto de cartas y el número de cartas que se extraen, tal como se describe en el enunciado.
- Esta función debe devolver la razón solicitada.
- Esta función se llamará exactamente una vez en cada prueba.
Restricciones
- $1\le N\le 10^6$
- $1\le K\le 100$
Subtareas
| Subtareas | Puntos | Restricciones adicionales | Dependencias |
|---|---|---|---|
| 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 | Sin restricciones adicionales | 1, 2, 3, 4 |
Ejemplos
oyun(2, 1)
La llamada anterior debe devolver $600000005$.
Nuestros números son $1,2,3,4,5$. Extraeremos 2 cartas. En la situación normal, podemos extraerlas de 20 formas diferentes. En el juego modificado, si la primera carta es $1$, $2$, $4$ o $5$, hay 3 posibilidades diferentes para la segunda; si es $3$, hay 4 posibilidades diferentes para la segunda. Por tanto, hay un total de 16 posibilidades en el juego modificado. $\frac{16}{20}=\frac45$. Esta probabilidad equivale a $600000005$ con nuestro módulo.
Evaluador de ejemplo
El evaluador de ejemplo espera cada caso en el formato siguiente:
$$N\ K$$
Si la función solicitada devuelve correctamente un entero, imprimirá este resultado $R$ en el formato siguiente:
$$R$$