Cadenas de bits hermosas

Nos encantan las bit-strings (cadenas de bits). Consideramos especialmente hermosas aquellas que no tienen k ceros consecutivos. Dada una longitud n, ¿puedes calcular cuántas bit-strings de longitud n cumplen esta condición?

Entrada

La entrada contiene dos enteros n y k (1 ≤ k ≤ n ≤ 1000).

Salida

El programa debe imprimir la cantidad de bit-strings hermosas de longitud n. Dado que la respuesta puede ser muy grande, se solicita imprimirla módulo .

Ejemplos

Explicación

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