우표 구매하기

우체국에서 파는 우표 중 가격이 1원인 우표는 $N$종류, 2원인 우표는 $M$종류가 있다. 종류가 다르면 서로 다른 우표로 센다.

정확히 $K$원어치를 구매하는 방법의 수를 구해 $P$로 나눈 나머지를 출력하는 프로그램을 작성하시오.

같은 종류의 우표를 여러 장 사도 되고, 우체국의 재고는 무한하다. 사는 순서는 구분하지 않으므로, 각 종류를 몇 장씩 샀는지가 같으면 같은 방법이다. 돈을 남기지 않고 정확히 $K$원을 모두 써야 한다.

첫째 줄에 $N$, $M$, $K$, $P$가 공백으로 구분되어 주어진다. ($0 \le N, M \le 300$, $1 \le K \le 10^{12}$, $3 \le P \le 1{,}000{,}000$, $P$는 소수)

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