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.</p>

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

입력 형식

Tekstifaili ainsal real on neli tühikutega eraldatud täisarvu: $N$, $V$, $T$ ja $K$ ($0 \le N \le 10^9$, $0 \le V \le 10^9$, $0 \le T \le 10^{18}$, $0 < K \le 10^9$).

출력 형식

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

예제 입력 1

1 3 2 100

예제 출력 1

11

예제 입력 2

0 10 1 20

예제 출력 2

0