박테리아

유쿠(Juku)가 저녁에 양치를 깜빡하는 바람에 입 속에서 박테리아가 번식하기 시작했습니다. 각 박테리아는 어린 박테리아이거나 성체 박테리아입니다. 매초 성체 박테리아 하나하나가 새로운 어린 박테리아를 한 마리씩 낳으며, 갓 태어난 어린 박테리아는 그 다음 초에 스스로 성체가 됩니다. 어떤 박테리아도 절대 죽지 않습니다.

처음에 어린 박테리아가 $N$마리, 성체 박테리아가 $V$마리 있을 때, $T$초 뒤 유쿠의 입 속에 있는 박테리아(어린 박테리아와 성체 박테리아를 합한 수)가 몇 마리인지 구하세요. 실제 개수 대신, 그 값을 주어진 수 $K$로 나눈 나머지를 출력합니다.

한 줄에 공백으로 구분된 네 개의 정수 $N$, $V$, $T$, $K$가 주어집니다 ($0 \le N \le 10^9$, $0 \le V \le 10^9$, $0 \le T \le 10^{18}$, $0 < K \le 10^9$).

$(X \bmod K)$ 값을 한 줄에 출력합니다. 여기서 $X$는 $T$초 뒤 유쿠의 입 속 박테리아의 총 개수이고, "$\bmod$"는 나눗셈의 나머지를 뜻합니다.