33212번 - EA Enigma 다국어

Nakon što je jednog mirnog subotnjeg poslijepodneva Josip otvorio laptop, primijetio je da je zaboravio izaći iz jedne aplikacije. Shvativši da je to bila neka zagonetna igra, odlučio ju je jedanput odigrati.

Pravila su bila jednostavna: treba pogoditi skrivenu riječ. Radi se o riječi duljine $N$, u kojoj su slova označena brojevima od $1$ do $K$. Kada igrač pogađa riječ, igra mu odgovara koje su sve pozicije u riječi dobro pogođene. Jednom kada igrač pogodi riječ igra završava. Rezultat igre je broj pokušaja pogađanja riječi.

Josip je znatiželjan pa od vas traži pomoć da mu odredite očekivani rezultat igre ako on igra optimalno i ako je skrivena riječ nasumično odabrana.

Ako rezultat predstavimo kao razlomak $\frac{p}{ q}$, ispišite $p \cdot q^{-1} \bmod {10^9 + 7}$. (Može se pokazati da je za svaki ekvivalentan razlomak ovaj rezultat jednak.)

U prvom retku nalaze se prirodni brojevi $N$ i $K$ ($1 ≤ N ≤ 10^6$, $1 ≤ K ≤ 10^9$).

U jedinom retku ispišite traženi rezultat.

Pojašnjenje trećeg probnog primjera: Očekivana vrijednost iznosi $\frac{1}{ 8} + 2 \cdot \frac{7}{ 8} = \frac{15}{8}$. Dalje vrijedi, $15 \cdot 8^{-1} \bmod {10^9 + 7} = 875000008$.