Красивые битовые строки

Мы обожаем битовые строки. Особенно красивыми мы считаем те, в которых нет k подряд идущих нулей. Пусть у нас есть длина n. Сможете ли вы найти количество различных битовых строк длины n, которые удовлетворяют этому условию?

Входные данные

Во входных данных содержатся два целых числа n и k (1 ≤ k ≤ n ≤ 1000).

Выходные данные

Программа должна вывести количество красивых битовых строк длины 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