시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB218543823.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로 나눈 나머지를 출력한다.

예제 입력 1

0 10 2 47

예제 출력 1

10

예제 입력 2

2 2 4 47

예제 출력 2

14

예제 입력 3

5 5 10 47

예제 출력 3

6
W3sicHJvYmxlbV9pZCI6IjEzNTQyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNmIwXHVkNDVjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YWUzMCAoSGFyZCkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZiMFx1Y2NiNFx1YWQ2ZFx1YzVkMFx1YzExYyBcdWQzMGNcdWIyOTQgXHVjNmIwXHVkNDVjIFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWFjYTlcdWM3NzQgMVx1YzZkMFx1Yzc3OCBcdWM2YjBcdWQ0NWNcdWIyOTQgXHVjZDFkIE5cdWM4ODVcdWI5NThcdWFjMDAgXHVjNzg4XHVhY2UwLCAyXHVjNmQwXHVjNzc4IFx1YzZiMFx1ZDQ1Y1x1YjI5NCBcdWNkMWQgTVx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1ZDQ1Y1x1Yjk3YyBLXHVjNmQwXHVjNWI0XHVjZTU4IFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWFjMTlcdWM3NDAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzZiMFx1ZDQ1Y1x1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YzBhY1x1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzAsIFx1YzZiMFx1Y2NiNFx1YWQ2ZFx1YzVkMFx1YjI5NCBcdWM2YjBcdWQ0NWNcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwIFx1YjljY1x1ZDA3YyBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBLXHVjNmQwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOLCBNLCBLLCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBOLCBNICZsZTsgMzAwLCAxICZsZTsgSyAmbGU7IDEwPHN1cD4xMjxcL3N1cD4sIDMgJmxlOyBQICZsZTsgMSwwMDAsMDAwLCBQXHViMjk0IFx1YzE4Y1x1YzIxOCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiMFx1ZDQ1Y1x1Yjk3YyBcdWMwYWNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBQXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEzNTQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTG92ZWx5IHN0YW1wcyAoSGFyZCkiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBQZXRlciBpcyBjb2xsZWN0aW5nIHN0YW1wcy4gUmVjZW50bHksIGhlIHdlbnQgc2hvcHBpbmcgd2l0aCBoaXMgbW90aGVyIEx1Y2lhIGFuZCBndWVzcyB3aGF0OiBBcyB0aGV5IHdlcmUgZ29pbmcgYXJvdW5kIHRoZSBwb3N0IG9mZmljZSwgaGUgc3RhcnRlZCB0byBibGFja21haWwgaGlzIG1vbSwgYXMgb25seSB0aGUgbGl0dGxlIGJveXMgY2FuLiBBdCB0aGUgcG9zdCBvZmZpY2UsIHRoZXkgd2VyZSBzZWxsaW5nIE4gZGlmZmVyZW50IHR5cGVzIG9mIG9uZS1kb2xsYXIgc3RhbXBzIGFuZCBNIGRpZmZlcmVudCB0eXBlcyBvZiB0d28tZG9sbGFyIHN0YW1wcy48XC9wPlxyXG5cclxuPHA+UGV0ZXIgZ290IGV4YWN0bHkgSyBkb2xsYXJzIGZyb20gaGlzIG1vbSwgYW5kIGhlIHdhbnRzIHRvIHNwZW5kIGFsbCBvZiB0aGVtIG9uIHN0YW1wcy4gTm90ZSB0aGF0IGhlIGNhbiBidXkgbW9yZSBzdGFtcHMgb2YgdGhlIHNhbWUgdHlwZS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgcG9zdCBvZmZpY2UgaGFzIGFuIGluZmluaXRlIHN0b2NrIG9mIGVhY2ggdHlwZSBvZiBzdGFtcC48XC9wPlxyXG5cclxuPHA+Tm93LCBQZXRlciBpcyB3b25kZXJpbmcgaW4gaG93IG1hbnkgd2F5cyBoZSBjYW4gYnV5IHRoZSBzdGFtcHMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGFyZSB0aGUgaW50ZWdlcnMgTiwgTSwgSywgYW5kIGEgcHJpbWUgbnVtYmVyIFAuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBjb21wdXRlIHRoZSB2YWx1ZSBaIG1vZCBQLCB3aGVyZSBaIGlzIHRoZSAocG9zc2libHkgaHVnZSkgbnVtYmVyIG9mIHdheXMgaW4gd2hpY2ggUGV0ZXIgY2FuIHNwZW5kIGFsbCBLIGRvbGxhcnMgb24gc3RhbXBzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+U2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgaW50ZWdlcnMgTiwgTSwgSywgYW5kIFAuJm5ic3A7WW91IG1heSBhc3N1bWUgdGhhdCAzICZsZTsgUCAmbGU7IDEwMDAwMDAsJm5ic3A7MCAmbGU7IE4sTSAmbGU7IDMwMCBhbmQgMSAmbGU7IEsgJmxlOyAxMDAwMDAwMDAwMDAwID0gMTA8c3VwPjEyPFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXI6IFRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gYnV5IHN0YW1wcywgbW9kdWxvIFAuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCB0ZXN0IGNhc2UsIHdlIG11c3QgYnV5IG9uZSAyLWRvbGxhciBzdGFtcCBhbmQgdGhlcmUgYXJlIDEwIHR5cGVzLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgc2Vjb25kIHRlc3QgY2FzZSwgd2UgaGF2ZSB0aGVzZSBvcHRpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmJ1eSB0d28gMi1kb2xsYXIgc3RhbXBzOiAzIHdheXMgdG8gZG8gc288XC9saT5cclxuXHQ8bGk+YnV5IGEgMi1kb2xsYXIgc3RhbXAgYW5kIHR3byAxLWRvbGxhciBzdGFtcHM6Jm5ic3A7MiZuYnNwOyZ0aW1lczsmbmJzcDszID0gNiZuYnNwO3dheXMgdG8gZG8gc288XC9saT5cclxuXHQ8bGk+YnV5IGZvdXIgMS1kb2xsYXIgc3RhbXBzOiA1IHdheXMgdG8gZG8gc288XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGVyZWZvcmUgdGhlIGFuc3dlciBpcyZuYnNwOygzICsgNiArIDUpIG1vZCA0NyA9IDE0IG1vZCA0NyA9IDE0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Internet Problem Solving Contest > IPSC 2010 L2번