우체국에서 파는 우표 중에서 가격이 1원인 우표는 총 N종류가 있고, 2원인 우표는 총 M종류가 있다.

우표를 K원어치 구매하는 방법의 수를 구하는 프로그램을 작성하시오.

같은 종류의 우표를 여러 개 사도 가능하며, 우체국에는 우표가 무한대 만큼 있다. 정확하게 K원을 모두 사용해야 한다.

입력 형식

첫째 줄에 N, M, K, P가 주어진다. (0 ≤ N, M ≤ 300, 1 ≤ K ≤ 10¹², 3 ≤ P ≤ 1,000,000, P는 소수)

출력 형식

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

예제 입력 1

0 10 2 47

예제 출력 1

10

예제 입력 2

2 2 4 47

예제 출력 2

14

예제 입력 3

5 5 10 47

예제 출력 3

6