시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 27 11 8 38.095%

문제

우체국에서 파는 우표 중에서 가격이 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
W3sicHJvYmxlbV9pZCI6IjEzNTQyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNmIwXHVkNDVjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNmIwXHVjY2I0XHVhZDZkXHVjNWQwXHVjMTFjIFx1ZDMwY1x1YjI5NCBcdWM2YjBcdWQ0NWMgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YWNhOVx1Yzc3NCAxXHVjNmQwXHVjNzc4IFx1YzZiMFx1ZDQ1Y1x1YjI5NCBcdWNkMWQgTlx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWM3ODhcdWFjZTAsIDJcdWM2ZDBcdWM3NzggXHVjNmIwXHVkNDVjXHViMjk0IFx1Y2QxZCBNXHVjODg1XHViOTU4XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHVkNDVjXHViOTdjIEtcdWM2ZDBcdWM1YjRcdWNlNTggXHVhZDZjXHViOWU0XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWMxOVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHVjNmIwXHVkNDVjXHViOTdjIFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjMGFjXHViM2M0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3MCwgXHVjNmIwXHVjY2I0XHVhZDZkXHVjNWQwXHViMjk0IFx1YzZiMFx1ZDQ1Y1x1YWMwMCBcdWJiMzRcdWQ1NWNcdWIzMDAgXHViOWNjXHVkMDdjJm5ic3A7XHVjNzg4XHViMmU0LiBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgS1x1YzZkMFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSwgSywgUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgTiwgTSAmbGU7IDMwMCwgMSAmbGU7IEsgJmxlOyAxMDxzdXA+MTI8XC9zdXA+LCAzICZsZTsgUCAmbGU7IDEsMDAwLDAwMCwgUFx1YjI5NCBcdWMxOGNcdWMyMTgpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2YjBcdWQ0NWNcdWI5N2MgXHVjMGFjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgUFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMzU0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxvdmVseSBzdGFtcHMiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBQZXRlciBpcyBjb2xsZWN0aW5nIHN0YW1wcy4gUmVjZW50bHksIGhlIHdlbnQgc2hvcHBpbmcgd2l0aCBoaXMgbW90aGVyIEx1Y2lhIGFuZCBndWVzcyB3aGF0OiBBcyB0aGV5IHdlcmUgZ29pbmcgYXJvdW5kIHRoZSBwb3N0IG9mZmljZSwgaGUgc3RhcnRlZCB0byBibGFja21haWwgaGlzIG1vbSwgYXMgb25seSB0aGUgbGl0dGxlIGJveXMgY2FuLiBBdCB0aGUgcG9zdCBvZmZpY2UsIHRoZXkgd2VyZSBzZWxsaW5nIE4gZGlmZmVyZW50IHR5cGVzIG9mIG9uZS1kb2xsYXIgc3RhbXBzIGFuZCBNIGRpZmZlcmVudCB0eXBlcyBvZiB0d28tZG9sbGFyIHN0YW1wcy48XC9wPlxyXG5cclxuPHA+UGV0ZXIgZ290IGV4YWN0bHkgSyBkb2xsYXJzIGZyb20gaGlzIG1vbSwgYW5kIGhlIHdhbnRzIHRvIHNwZW5kIGFsbCBvZiB0aGVtIG9uIHN0YW1wcy4gTm90ZSB0aGF0IGhlIGNhbiBidXkgbW9yZSBzdGFtcHMgb2YgdGhlIHNhbWUgdHlwZS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgcG9zdCBvZmZpY2UgaGFzIGFuIGluZmluaXRlIHN0b2NrIG9mIGVhY2ggdHlwZSBvZiBzdGFtcC48XC9wPlxyXG5cclxuPHA+Tm93LCBQZXRlciBpcyB3b25kZXJpbmcgaW4gaG93IG1hbnkgd2F5cyBoZSBjYW4gYnV5IHRoZSBzdGFtcHMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGFyZSB0aGUgaW50ZWdlcnMgTiwgTSwgSywgYW5kIGEgcHJpbWUgbnVtYmVyIFAuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBjb21wdXRlIHRoZSB2YWx1ZSBaIG1vZCBQLCB3aGVyZSBaIGlzIHRoZSAocG9zc2libHkgaHVnZSkgbnVtYmVyIG9mIHdheXMgaW4gd2hpY2ggUGV0ZXIgY2FuIHNwZW5kIGFsbCBLIGRvbGxhcnMgb24gc3RhbXBzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+U2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgaW50ZWdlcnMgTiwgTSwgSywgYW5kIFAuJm5ic3A7WW91IG1heSBhc3N1bWUgdGhhdCAzICZsZTsgUCAmbGU7IDEwMDAwMDAsJm5ic3A7MCAmbGU7IE4sTSAmbGU7IDMwMCBhbmQgMSAmbGU7IEsgJmxlOyAxMDAwMDAwMDAwMDAwID0gMTA8c3VwPjEyPFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXI6IFRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gYnV5IHN0YW1wcywgbW9kdWxvIFAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Internet Problem Solving Contest > IPSC 2010 L번