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.