Beautiful bit-strings

We love bit-strings. We especially consider those beautiful if they don’t have k consecutive 0s. Given a length n, can you count the number of different bit-strings of length n that are beautiful?

Input

The input contains two integers n and k (1 ≤ k ≤ n ≤ 1000).

Output

The program should print the number of beautiful bit-strings of length n. As the answer can be very large, you are asked to print it modulo .

Examples

Explanation

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