Stringhe di bit bellissime

Amiamo le stringhe di bit. Consideriamo particolarmente “bellissime” quelle in cui ogni sequenza di zeri consecutivi ha una lunghezza massima di k. Dato un valore di lunghezza n, sai calcolare quante stringhe di bit di lunghezza n rispettano questa proprietà?

Ingresso

L’ingresso contiene due interi n e k (1 ≤ k ≤ n ≤ 1000).

Uscita

Il programma deve stampare il numero di stringhe di bit “bellissime” di lunghezza n. Poiché il risultato può essere molto grande, devi stamparlo in modulo .

Esempi

Spiegazione

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