Chaînes de bits « belles »

Nous aimons beaucoup les chaînes de bits (bit-strings). Nous considérons qu’une chaîne de bits est « belle » si elle ne contient pas k zéros consécutifs. Étant donné une longueur n, pouvez-vous déterminer combien de chaînes de bits distinctes de longueur n satisfont à ce critère ?

Entrée

Les données d’entrée contiennent deux entiers n et k (1 ≤ k ≤ n ≤ 1000).

Sortie

Le programme doit afficher le nombre de chaînes de bits « belles » de longueur n. Comme la réponse peut être très grande, vous devez l’afficher modulo .

Exemples

Explication

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