시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 3 | 2 | 2 | 100.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:
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.
3 2
5
3 3
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}