우표 구매하기 (Easy)
시간 제한1초메모리 제한1024 MB
1원짜리 N종류와 2원짜리 M종류의 우표를 무한히 쓸 수 있을 때 정확히 K원어치를 사는 방법의 수를 소수 P로 나눈 나머지를 구한다.
문제
우체국에서 파는 우표 중에서 가격이 1원인 우표는 총 N종류가 있고, 2원인 우표는 총 M종류가 있다.
우표를 K원어치 구매하는 방법의 수를 구하는 프로그램을 작성하시오.
같은 종류의 우표를 여러 개 사도 가능하며, 우체국에는 우표가 무한대 만큼 있다. 정확하게 K원을 모두 사용해야 한다.
입력
첫째 줄에 N, M, K, P가 주어진다. (0 ≤ N, M ≤ 1000, 1 ≤ K ≤ 1000, 3 ≤ P ≤ 1,000,000, P는 소수)
출력
첫째 줄에 우표를 사는 방법의 수를 P로 나눈 나머지를 출력한다.