Գեղեցիկ bit-string-եր
Մենք սիրում ենք բիթ-տողեր և դրանք հատկապես գեղեցիկ ենք համարում, եթե դրանց մեջ չի հանդիպում
k անընդմեջ 0-ների հաջորդականություն։ Ունենալով n երկարությունը, կարո՞ղ եք հաշվել, թե քանի տարբեր բիթ-տողեր կարելի է կազմել, որոնք համարում ենք գեղեցիկ։Մուտք
Մուտքի միակ տողում տրված են երկու ամբողջ թվեր
n և k (1 ≤ k ≤ n ≤ 1000)։Ելք
Ծրագիրը պետք է տպի
n երկարություն ունեցող գեղեցիկ բիթ-տողերի քանակը։ Քանի որ պատասխանը կարող է շատ մեծ լինել, խնդրում ենք տպել պատասխանը -ի բաժանելիս ստացվող մնացորդը։Օրինակներ
Մուտք | Ելք |
5 2 | 24 |
Բացատրություն
- 00100
- 00101
- 00110
- 00111
- 01001
- 01010
- 01011
- 01100
- 01101
- 01110
- 01111
- 10010
- 10011
- 10100
- 10101
- 10110
- 10111
- 11001
- 11010
- 11011
- 11100
- 11101
- 11110
- 11111
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB