美しいビット列

私たちはビット列が大好きです。特に、連続した k 個の 0 が含まれないビット列を「美しい」と呼ぶことにします。長さが n のとき、こうした美しいビット列は全部でいくつあるでしょうか？

入力

入力には、2つの整数 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