Schöne Bit-Strings

Wir lieben Bit-Strings. Besonders interessant sind jene, die keine k aufeinanderfolgenden 0 enthalten. Angenommen, wir haben eine Bit-String-Länge n: Kannst du ermitteln, wie viele unterschiedliche Bit-Strings der Länge n diese Eigenschaft erfüllen?

Eingabe

Die Eingabe enthält zwei ganze Zahlen n und k (1 ≤ k ≤ n ≤ 1000).

Ausgabe

Dein Programm soll die Anzahl aller „schönen“ Bit-Strings der Länge n ausgeben. Da das Ergebnis sehr groß sein kann, soll es modulo berechnet werden.

Beispiele

Erklärung

1. 00100

2. 00101

3. 00110

4. 00111

5. 01001

6. 01010

7. 01011

8. 01100

9. 01101

10. 01110

11. 01111

12. 10010

13. 10011

14. 10100

15. 10101

16. 10110

17. 10111

18. 11001

19. 11010

20. 11011

21. 11100

22. 11101

23. 11110

24. 11111