Grasshopper-KMax
Problem
La cavalletta salta su colonne poste sulla stessa linea a uguale distanza l'una dall'altra. Le colonne hanno numeri di serie da 1 a N . All'inizio, la cavalletta siede su un palo con il numero 1. Può saltare in avanti da 1 a K barre, contando da quella attuale. È necessario trovare il numero di modi in cui il Grasshopper può arrivare alla colonna con il numero N. Tieni presente che la cavalletta non può saltare all'indietro.
Poiché il numero di modi per trovarlo può essere molto grande, modulo \(10^6 + 7\) , cioè trova il resto della divisione a cui questo numero \(10^6 + 7\) .
Input: La stringa di input contiene i numeri naturali N e K separati da uno spazio. È garantito che \(1 <= N ,\ K <= 10000\).
Output: Il programma dovrebbe stampare un singolo numero: il numero di modi in cui Grasshopper può arrivare alla colonna numerata N calcolata dal modulo \(10^6+7\).
Esempi
| # |
Input |
Uscita |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |