시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB322100.000%

문제

Gospodin Malnar odlučio je ove godine organizirati novogodišnju proslavu na koju će pozvati svojih n najboljih prijatelja. Budući da se radi o najluđoj noći u godini, svakom će prijatelju pokloniti jednu gljivu pomoću koje će taj prijatelj naručenu pizzu margheritu pretvoriti u capricciosu.

Gospodin Malnar inače posjeduje beskonačno mnogo gljiva, a svaku je od njih označio različitim nenegativnim cijelim brojem. Prije početka same zabave, gljive će staviti u vreću iz koje će svaki gost izvući svoju gljivu. Nažalost, nije uspio nabaviti dovoljno veliku vreću u koju bi stale sve gljive i sada nikako ne može odrediti koje će gljive staviti u vreću. Nakon što je još malo razmislio, donio je sljedeću odluku:

  • Prije početka zabave u vreći će se nalaziti točno n gljiva.
  • Ako se u vreći nalazi gljiva s oznakom x > 0, tada se u vreći mora nalaziti i gljiva s oznakom ⌊(x−1)/k⌋.

Pomozite gospodinu Malnaru i odredite na koliko različitih načina može pripremiti vreću gljiva za novogodišnju zabavu.

Napomena: Budući da traženi broj načina može biti vrlo velik, potrebno je samo ispisati njegov ostatak pri djeljenju s 109 + 7.

입력

U prvom su retku prirodni brojevi n (2 ≤ n ≤ 1 000 000) i k (1 ≤ k ≤ 1 000 000).

출력

U prvom retku ispišite traženi broj načina modulo 109 + 7.

예제 입력 1

3 2

예제 출력 1

5

예제 입력 2

3 3

예제 출력 2

12

힌트

Pojašnjenje prvog probnog primjera: moguće vreće su {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 2, 5} i {0, 2, 6}