Grasshopper-KMax
Problem
O gafanhoto salta em colunas localizadas na mesma linha a distâncias iguais umas das outras. As colunas têm números de série de 1 a N . No início, o Gafanhoto senta-se em um poste com o número 1. Ele pode avançar de 1 para K barras, contando a partir da atual. É necessário encontrar o número de maneiras pelas quais o Grasshopper pode chegar à coluna com o número N. Tenha em mente que o Gafanhoto não pode pular para trás.
Como o número de maneiras de encontrar pode ser muito grande, modulo \(10^6 + 7\) , ou seja, encontre o resto da divisão desse número para \(10^6 + 7\) .
Entrada: A string de entrada contém números naturais N e K separados por um espaço. É garantido que \(1 <= N ,\ K <= 10000\).
Saída: O programa deve imprimir um único número: o número de maneiras que o Grasshopper pode chegar à coluna numerada N calculado do módulo \(10^6+7\).
Exemplos
| # |
Entrada |
Saída |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |