Problem
El saltamontes salta sobre columnas ubicadas en la misma línea a la misma distancia entre sí. Las columnas tienen números de serie de 1 a N . Al principio, el saltamontes se sienta en un poste con el número 1. Puede saltar de barras 1 a K, contando desde la barra actual. Se requiere encontrar el número de formas en que el Grasshopper puede llegar a la columna con el número N. Tenga en cuenta que el saltamontes no puede saltar hacia atrás.
Dado que la cantidad de formas de encontrar puede ser muy grande, modulo \(10^6 + 7\) , es decir, encuentre el resto de la división a la que corresponde este número \(10^6 + 7\) .
Entrada: La cadena de entrada contiene números naturales N y K separados por un espacio. Se garantiza que \(1 <= N ,\ K <= 10000\).
Salida: El programa debe imprimir un solo número: el número de formas en que el Saltamontes puede llegar a la columna numerada N calculada del módulo \(10^6+7\).
Ejemplos
| # |
Entrada |
Salida |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |