우표 구매하기

우체국에서 파는 우표 가운데 가격이 1원인 우표는 $N$종류, 2원인 우표는 $M$종류이다.

우표를 사서 정확히 $K$원어치가 되는 방법의 수를 구하는 프로그램을 작성하시오.

같은 종류의 우표는 여러 장 사도 되며, 우체국에는 각 우표가 무한히 있다. 반드시 $K$원을 전부 써야 한다.

첫째 줄에 $N$, $M$, $K$, $P$가 주어진다. ($0 \le N, M \le 1000$, $1 \le K \le 1000$, $3 \le P \le 1{,}000{,}000$, $P$는 소수이다.)

첫째 줄에 우표를 사는 방법의 수를 $P$로 나눈 나머지를 출력한다.