시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 21 9 7 43.750%

문제

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

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

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

입력

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

출력

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

예제 입력

0 10 2 47

예제 출력

10

예제 입력 2

2 2 4 47

예제 출력 2

14

예제 입력 3

5 5 10 47

예제 출력 3

6

힌트

출처

Contest > Internet Problem Solving Contest > IPSC 2010 L번