Problem
Die Heuschrecke springt in gleicher Entfernung voneinander über die Pfosten, die sich auf derselben Linie befinden. Die Spalten haben Sequenznummern von 1 bis N . Am Anfang sitzt die Heuschrecke auf einer Spalte mit der Nummer 1. Er kann in einer Entfernung von 1 zu K Säulen vorwärts springen, wobei er vom aktuellen zählt. Es ist erforderlich, die Anzahl der Möglichkeiten zu finden, wie eine Heuschrecke die Spalte mit der Nummer N erreichen kann. Beachten Sie, dass die Heuschrecke nicht rückwärts springen kann.
Da die Anzahl der zu findenden Methoden sehr groß sein kann, berechnen Sie sie modulo \(10^6 + 7\) , dh finde den Rest der Division dieser Zahl durch \(10^6 + 7\) .
Eingabe: Die Eingabezeichenfolge enthält die natürlichen Zahlen N und K, getrennt durch ein Leerzeichen. Es ist garantiert, dass \(1 <= N ,\ K <= 10000\).
Ausgabe: Das Programm sollte eine Zahl ausgeben: die Anzahl der Möglichkeiten, wie eine Heuschrecke auf die Spalte mit der Nummer N gelangen kann , berechnet modulo \(10^6+7\).
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |