CSES - Bittijonot I
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Tehtäväsi on laskea, montako $n$ bitin jonoa on olemassa, jossa pisin samaa bittiä toistava osuus on enintään $k$ bitin mittainen.

Koska vastaus voi olla suuri, tulosta se modulo $10^9+7$.

Syöte

Syötteenä on kaksi kokonaislukua $n$ ja $k$.

Tuloste

Tulosta vastaus tehtävään.

Rajat
  • $1 \le n \le 10^6$
  • $1 \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.