Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Bittijonot II


Task | Statistics


CSES - Bittijonot IICSES - Bittijonot II

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 vähintää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
Esimerkki

Syöte:
4 2

Tuloste:
14

Selitys: Bittijonot ovat 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1100, 1101, 1110 ja 1111.