Problem E
Eindahraðall

Verið er að setja upp eindahraðal á Íslandi. Hraðallinn er $N$ Planck lengdir að lengd og liggur í hring. Nú er verið að skipuleggja tilraun þar sem skella á tveimur eindum saman. Í byrjun er rafeind sett í hringinn og hraða seglarnir henni áfram. Rafeindin ferðast ávallt heiltölufjölda Planck lengda áfram. Þar sem hún er að fara hraðar og hraðar ferðast hún ávallt lengra en síðast. Í fyrsta skrefi eru helmingslíkur að hún fari eina Planck lengd, fjórðungslíkur að hún fari tvær og svo framvegis. Eins ef hún ferðaðist $k$ Planck lengdir síðast eru helmingslíkur að hún fari $k+1$ næst, fjórðungslíkur að hún fari $k+2$ næst og svo framvegis. Þegar eindin færist um $\ge N$ Planck lengdir í einu halda seglarnir ekki í við að halda henni inn á brautinni. Því viljum við skella henni á aðra eind á þeirri agnarstundu sem það gerist. Til þess þarf eindin að vera komin þar sem hún byrjaði þegar þetta gerist. Hverjar eru líkurnar á því?

Til dæmis, ef $N=7$ gæti hún farið tvær Planck lengdir áfram, svo þrjár og loks sex áður en hún þarf að vera komin á upphafspunkt. Í þessu dæmi endar hún ekki þar aftur, en margir aðrir ferlar koma til greina. Til að átta okkur á hversu oft fráhrindandi áhrifin koma til leiks höfum við áhuga á líkunum á að eindin verði á upphafspunkti þegar rannsókn lýkur. Ef eindin er í upphafspunkti er jafn líklegt að hún fari til vinstri og að hún fari til hægri. Ef eindin færðist um $k$ skref síðast er jafn líklegt að hún taki $k+1$ skref og að hún taki fleiri. Eins er jafn líklegt að hún taki $k+2$ og hún taki fleiri, svo það eru helmingslíkur á $k+1$, fjórðungslíkur á $k+2$ og svo framvegis.

Inntak

Fyrsta línan inniheldur eina tölu $1\le t\le 100$, fjölda prófunartilfella. Svo koma $t$ línur, hver með einni heiltölu $1\le N\le {10}^{18}$.

Úttak

Fyrir hvert $N$ í inntaki skal prenta líkunum sem lýst er að ofan fyrir það $N$ á sinni eigin línu. Líkurnar má rita sem fullstytt brot $p/q$. Þar sem þessar tölur gætu verið mjög stórar skal í staðinn prenta $p{q}^{-1}$ mátað við $1000000007$, þar sem $q^{-1}$ er margföldunarandhverfa $q$ með tilliti til mátunar við $1000000007$.

Til dæmis, ef $p=2$ og $q=4$, þá finnum við heiltöluna $q^{-1}$ sem uppfyllir $q\cdot q^{-1}\equiv 1(\mathrm{mod}1000000007)$. Þar sem $4\cdot 250000002=1000000008$ og $1000000008\equiv 1(\mathrm{mod}1000000007)$ getum við reiknað út $p{q}^{-1}\equiv 2\cdot 250000002\equiv 500000004(\mathrm{mod}1000000007)$.

5
1
2
3
4
100

1
500000004
500000004
250000002
263762378