Une personne qui joue au summum des jeux mobiles se met un jour très en colère contre le jeu auquel elle doit jouer alors qu'elle essaie de signer un contrat. Le jeu fonctionne ainsi :
- Un ensemble de cartes porte les nombres de $1$ à $2N+K$.
- Le jeu tire $N$ cartes une à une dans cet ensemble, sans remise : un nombre ne peut pas être tiré deux fois.
- Après les cartes tirées, le joueur prédit si la carte suivante sera plus grande ou plus petite.
Ce qui met le joueur en colère, c'est que, par malchance, un nombre encore plus petit suit constamment un petit nombre, et un nombre encore plus grand suit constamment un grand nombre. Pour éviter cela, le joueur modifie le mécanisme aléatoire du jeu. Sa modification ajoute les deux règles suivantes au tirage :
- Si une carte portant un nombre de $1$ à $N$ est tirée, le nombre de la carte suivante doit être strictement supérieur à $N$ ($>N$).
- Si une carte portant un nombre de $N+K+1$ à $2N+K$ est tirée, le nombre de la carte suivante doit être strictement inférieur à $N+K+1$ ($<N+K+1$).
Après ces modifications, le joueur se demande à quel point il a perturbé le jeu. Il le mesure par le rapport entre le nombre de suites de tirages différentes possibles dans la version modifiée et le nombre de suites de tirages possibles dans la version normale. Il vous demande ce rapport modulo $10^9+7$.
Détails d'implémentation
Vous devez implémenter la fonction suivante :
int oyun(int N, int K)- $N$ et $K$ sont les entiers qui déterminent l'ensemble de cartes et le nombre de cartes tirées, comme indiqué dans l'énoncé.
- Cette fonction doit renvoyer le rapport demandé.
- Cette fonction sera appelée exactement une fois par test.
Contraintes
- $1\le N\le 10^6$
- $1\le K\le 100$
Sous-tâches
| Sous-tâche | Points | Contraintes supplémentaires | Dépendances |
|---|---|---|---|
| 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 | Aucune contrainte supplémentaire | 1, 2, 3, 4 |
Exemples
oyun(2, 1)
L'appel ci-dessus doit renvoyer $600000005$.
Nos nombres sont $1,2,3,4,5$. Nous tirons 2 cartes. Dans le jeu normal, il y a 20 façons de tirer les cartes. Dans le jeu modifié, si la première carte est $1$, $2$, $4$ ou $5$, il y a 3 possibilités pour la seconde ; si elle est $3$, il y en a 4. Il y a donc 16 possibilités dans le jeu modifié. $\frac{16}{20}=\frac45$. Cette probabilité est équivalente à $600000005$ pour notre module.
Évaluateur d'exemple
L'évaluateur d'exemple attend chaque cas au format suivant :
$$N\ K$$
Si la fonction demandée renvoie correctement un entier, il affiche ce résultat $R$ au format suivant :
$$R$$