美しいビット列
私たちはビット列が大好きです。特に、連続した
k 個の 0 が含まれないビット列を「美しい」と呼ぶことにします。長さが n のとき、こうした美しいビット列は全部でいくつあるでしょうか？入力
入力には、2つの整数
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