Problem C
Gagnageymsla

Upplýsingatæknisvið Háskóla Íslands vistar ógrynni af gögnum fyrir hönd nemenda og starfsmanna, mikið af því gögnum sem tölvurnar skrá sjálfkrafa um notkun tölvuþjónusta, álag á tölvukerfum og alls kyns fleira. Á hverju ári safnast því mikið af gögnum í gagnaver sviðsins og til að koma í veg fyrir að klára geymslupláss er hreinsað til í lok árs. En nú er verið að plana fram í tíman og áætla hvað þarf að vera til mikið geymslupláss til að dekka þarfir framtíðarinnar. Til þess ert þú fenginn til að meta þarfirnar.

Við vitum að næstu ár mun sviðið þurfa skrá hjá sér $N$ gígabæt af gögnum samtals. Á hverju ári mun sviðið skrá hjá sér alla vega $1$ gígabæt og í mesta lagi $M$ gígabæti. Við lítum svo á að allar leiðir til að skrá hjá sér $N$ gígabæt yfir einhvern fjölda ára svo a.m.k. eitt gígabæt sé skráð á ári séu jafn líklegar útkomur. T.d. fyrir $N = 4$ eru $8$ valkostir, t.d. mætti skrá $1$ gígabæt á hverju ári í fjögur ár eða $3$ fyrsta árið og $1$ annað árið. Í lok hvers árs þegar gögn eru grisjuð mun flestum gögnum vera hent, en ekki öllum. Nánar tiltekið ef það eru $x$ gígabæt vistuð í lok árs munu vera $\sqrt{x}$ gígabæt eftir þegar grisjun er lokið. Athugið að sökum þess að sviðið notar nýmóðins skammtatölvur getur þetta orðið til þess að gögnin munu innihalda fjölda bita sem er ekki heiltala.

Rétt áður en að átti að fara í gang með þetta bárust þér auka upplýsingar frá einum prófessor. Hann sagði að hægt væri að gera spánna nákvæmari því hann vissi fyrir víst að í lok þessarra ára myndi fjöldi gígabæta sem væru vistaðar vera heiltala, grisjun síðasta ársins talin með. Þessar upplýsingar hjálpa gífurlega því það útilokar ansi marga möguleika. Aðspurður hvernig hann vissi þetta svaraði hann aðeins “nanóvélar” og lét sig hverfa. Að þessu öllu gefnu, hver er væntur fjöldi gígabæta vistaðar hjá sviðinu í lok ferlisins?

Sýnidæmi

Segjum að $N = 14$. Þá væri ein leið til að enda með heiltölufjölda að skrá $1, 8, 1, 2$ og $2$ gígabæt hvert ár, í þessarri röð. Þá væri fjöldi gígabæta eftir í kerfinu eftir grisjun $1, 3, 2, 2$ og $2$ hvert ár, í þessarri röð. Önnur jafn líkleg útkoma væri að skrá $2, 2, 1, 9$ gígabæt hvert ár, í þeirri röð. Í báðum þessum tilfellum er fjöldi gígabæta í lok ferlisins $2$.

Inntak

Inntakið inniheldur eina línu með tveimur heiltölum $1 \leq N, M \leq 5000$, fjöldi samtals skráðra gígabæta og hámarksfjöldi skráðra gígabæta á ári.

Úttak

Ef upplýsingar prófessorsins eru mótsagnarkenndar, þ.e. ef ekki er til nein leið til að enda með heiltölufjölda gígabæta að öðrum skilyrðum gefnum, prentið $-1$. Annars á að prenta á út væntan fjölda gígabæta í lok ferlisins að skilyrðunum að ofan gefnum. Líkurnar verða þá ávallt heiltölubrot á forminu $p / q$ með $q = 0$. Frekar en að prenta þetta brot á að prenta $pq^{-1} \pmod{10^9+7}$ þar sem $q^{-1}$ táknar margföldunarandhverfu $q$ þegar reikningar eru framkvæmdir mátað við $10^9 + 7$.

14 8

2

25 6

-1

100 50

891168391