Գեղեցիկ bit-string-եր

Մենք սիրում ենք բիթ-տողեր և դրանք հատկապես գեղեցիկ ենք համարում, եթե դրանց մեջ չի հանդիպում k անընդմեջ 0-ների հաջորդականություն։ Ունենալով 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