Uma pessoa que joga o auge dos jogos para telemóvel fica muito irritada com o jogo que tem de jogar enquanto tenta assinar um contrato num certo dia. O jogo funciona da seguinte forma:
- Existe um conjunto de cartas com números de $1$ a $2N+K$.
- O jogo retira $N$ cartas, uma a uma, deste conjunto (sem reposição, o que significa que um número não pode ser retirado duas vezes).
- Após as cartas retiradas, o jogador tenta adivinhar se a carta seguinte terá um número maior ou menor.
O que irrita o jogador é que, devido à sua má sorte, um número mais pequeno aparece constantemente depois de um número pequeno, e um número maior aparece constantemente depois de um número grande. Por isso, o jogador pretende evitar isto modificando o mecanismo de aleatoriedade do jogo. A alteração que faz acrescenta as duas regras seguintes à retirada de cartas:
- Se for retirada uma carta com um número de $1$ a $N$, o número da carta seguinte deve ser estritamente maior do que $N$ ($>N$).
- Se for retirada uma carta com um número de $N+K+1$ a $2N+K$, o número da carta seguinte deve ser estritamente menor do que $N+K+1$ ($<N+K+1$).
O jogador pergunta-se quanto estragou o jogo depois destas modificações. A medida de quanto o estragou é a razão entre o número de todas as sequências diferentes possíveis de retirada de cartas na versão modificada do jogo e o número de todas as sequências possíveis de retirada de cartas na versão normal. Pede-lhe esta razão módulo $10^9+7$.
Detalhes de implementação
Deve implementar a seguinte função:
int oyun(int N, int K)- $N$ e $K$ são inteiros que determinam o conjunto de cartas e o número de cartas a retirar, tal como referido no enunciado.
- Esta função deve devolver a razão pedida.
- Esta função será chamada exatamente uma vez em cada teste.
Restrições
- $1\le N\le 10^6$.
- $1\le K\le 100$.
Subtarefas e pontuação
| Subtarefa | Pontos | Restrições adicionais | Dependências |
|---|---|---|---|
| 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 | Sem restrições adicionais | 1, 2, 3, 4 |
Exemplos
oyun(2, 1)
Espera-se que a chamada de função acima devolva $600000005$.
Os nossos números são $1,2,3,4,5$. Vamos retirar 2 cartas. Numa situação normal, podemos retirar as cartas de 20 formas diferentes. No jogo modificado, se a primeira carta for $1$, $2$, $4$ ou $5$, existem 3 possibilidades diferentes para a segunda carta; se for $3$, existem 4 possibilidades diferentes para a segunda carta. Portanto, existem 16 possibilidades no total para o jogo modificado. $\frac{16}{20}=\frac45$. Esta probabilidade equivale a $600000005$ com o nosso módulo.
Avaliador de exemplo
O avaliador de exemplo espera cada caso no seguinte formato:
$$N\ K$$
Se a função pedida devolver com sucesso um inteiro, imprimirá esse resultado $R$ no seguinte formato:
$$R$$