Cadeias de bits bonitas

Nós adoramos bit-strings (cadeias de bits). Em especial, consideramos bonitas aquelas que não contêm k zeros consecutivos. Dado um comprimento n, consegue contar quantas bit-strings de comprimento n são consideradas bonitas?

Entrada

A entrada contém dois inteiros n e k (1 ≤ k ≤ n ≤ 1000).

Saída

O programa deve imprimir o número de bit-strings bonitas de comprimento n. Como a resposta pode ser muito grande, deve ser impressa em módulo .

Exemplos

Explicação

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