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