Bakterid

문제

Juku unustas õhtul hambaid pesta ning tema suus hakkasid paljunema bakterid. Iga bakter on kas noor või täiskavanu. Iga sekundi jooksul sünnitab iga täiskasvanu ühe uue noore bakteri, kes saab järgmise sekundi jooksul ise täiskasvanuks. Ükski bakter kunagi ei sure.

Leida, kui palju baktereid (noori ja täiskasvanuid kokku) on Juku suus $TT$ sekundi pärast, kui alguses on seal $NN$ noort ning $VV$ täiskasvanut. Tegeliku arvu asemel väljastada jääk, mis tekib selle jagamisel antud arvuga $KK$.

입력

Tekstifaili ainsal real on neli tühikutega eraldatud täisarvu: $NN$, $VV$, $TT$ ja $KK$ ($0\le N\le {10}^{9}0\; \backslash le\; N\; \backslash le\; 10^9$, $0\le V\le {10}^{9}0\; \backslash le\; V\; \backslash le\; 10^9$, $0\le T\le {10}^{18}0\; \backslash le\; T\; \backslash le\; 10^\{18\}$, ).

출력

Tekstifaili ainsale reale väljastada väärtus $(XK)(X\; \backslash bmod\; K)$, kus $XX$ on bakterite koguarv Juku suus $TT$ sekundi pärast ning "$\backslash bmod$" tähistab jagamisel tekkiva jäägi leidmist.