CSES - Bittijonot I
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tehtäväsi on laskea, montako nn bitin jonoa on olemassa, jossa pisin samaa bittiä toistava osuus on enintään kk bitin mittainen.

Koska vastaus voi olla suuri, tulosta se modulo 109+710^9+7.

Syöte

Syötteenä on kaksi kokonaislukua nn ja kk.

Tuloste

Tulosta vastaus tehtävään.

Rajat

  • 1n1061 \le n \le 10^6
  • 1k101 \le k \le 10

Esimerkki

Syöte:

4 2

Tuloste:

10

Selitys: Bittijonot ovat 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100 ja 1101.