시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB87291948.718%

문제

분수 중에서 분자가 1이고 분모가 양수인 것을 단위분수라고 한다. 분수 p/q를 유한개의 단위분수의 합으로 나타내었을 때 p/q를 단위분수로 분할했다고 말한다. 예를 들면 2/3는 1/2 + 1/6으로 분할 할 수 있다. 분할에서 더하기의 순서만 바뀐 것은 고려하지 않는다. 예를 들면 1/6 + 1/2와 1/2 + 1/6은 같은 분할로 본다.

네 개의 양의정수 p, q, a, n이 주어졌을 때 다음 두 조건을 만족하는 p/q의 분할의 개수를 구하여라.

  1. n개 이하의 단위분수의 합으로 나타내야 한다.
  2. 분할을 이루는 단위분수의 분모의 크기의 곱은 a보다 작거나 같아야 한다.

예를 들어 만약 (p, q, a, n)이 (2, 3, 120, 3)일 때 답은 4가 되어야 한다.

2/3 = 1/3 + 1/3 = 1/2 + 1/6 = 1/4 + 1/4 + 1/6 = 1/3 + 1/6 + 1/6

입력

첫째 줄에 양의 정수 p, q, a, n이 입력된다. (1 ≤ p, q ≤ 800, 1 ≤ a ≤ 12000, 1 ≤ n ≤ 7)

출력

첫째 줄에 문제의 조건을 만족하는 분할의 개수를 출력한다.

예제 입력 1

2 3 120 3

예제 출력 1

4

예제 입력 2

2 3 300 3

예제 출력 2

7

예제 입력 3

2 3 299 3

예제 출력 3

6

예제 입력 4

2 3 12 3

예제 출력 4

2

예제 입력 5

2 3 12000 7

예제 출력 5

42

예제 입력 6

54 795 12000 7

예제 출력 6

1

예제 입력 7

2 3 300 1

예제 출력 7

0

예제 입력 8

2 1 200 5

예제 출력 8

9

예제 입력 9

2 4 54 2

예제 출력 9

3
W3sicHJvYmxlbV9pZCI6IjI0MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM3MDQgXHViZDg0XHVjMjE4XHViODVjIFx1YmQ4NFx1ZDU2MCIsImRlc2NyaXB0aW9uIjoiPHA+XHViZDg0XHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWJkODRcdWM3OTBcdWFjMDAgMVx1Yzc3NFx1YWNlMCBcdWJkODRcdWJhYThcdWFjMDAgXHVjNTkxXHVjMjE4XHVjNzc4IFx1YWM4M1x1Yzc0NCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJkODRcdWMyMTggcFwvcVx1Yjk3YyBcdWM3MjBcdWQ1NWNcdWFjMWNcdWM3NTggXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWM1YzhcdWM3NDQgXHViNTRjIHBcL3FcdWI5N2MgXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHViODVjIFx1YmQ4NFx1ZDU2MFx1ZDU4OFx1YjJlNFx1YWNlMCBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMlwvM1x1YjI5NCAxXC8yICsgMVwvNlx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmQ4NFx1ZDU2MFx1YzVkMFx1YzExYyBcdWIzNTRcdWQ1NThcdWFlMzBcdWM3NTggXHVjMjFjXHVjMTFjXHViOWNjIFx1YmMxNFx1YjAxMCBcdWFjODNcdWM3NDAgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCAxXC82ICsgMVwvMlx1YzY0MCAxXC8yICsgMVwvNlx1Yzc0MCBcdWFjMTlcdWM3NDAgXHViZDg0XHVkNTYwXHViODVjIFx1YmNmOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NThcdWM4MTVcdWMyMTggcCwgcSwgYSwgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YjJlNFx1Yzc0YyBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBwXC9xXHVjNzU4IFx1YmQ4NFx1ZDU2MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPm5cdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YjJlOFx1YzcwNFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZDg0XHVkNTYwXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWM3NTggXHViZDg0XHViYWE4XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjZjFcdWM3NDAgYVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjljY1x1YzU3ZCAocCwgcSwgYSwgbilcdWM3NzQgKDIsIDMsIDEyMCwgMylcdWM3N2MgXHViNTRjIFx1YjJmNVx1Yzc0MCA0XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcLzMgPSAxXC8zICsgMVwvMyA9IDFcLzIgKyAxXC82ID0gMVwvNCArIDFcLzQgKyAxXC82ID0gMVwvMyArIDFcLzYgKyAxXC82PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggcCwgcSwgYSwgblx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7KDEgJmxlOyBwLCBxICZsZTsgODAwLCAxICZsZTsgYSAmbGU7IDEyMDAwLCAxICZsZTsgbiAmbGU7IDcpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCZuYnNwO1x1YmQ4NFx1ZDU2MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI0MDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJVbml0IEZyYWN0aW9uIFBhcnRpdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSBmcmFjdGlvbiB3aG9zZSBudW1lcmF0b3IgaXMgMSBhbmQgd2hvc2UgZGVub21pbmF0b3IgaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGlzIGNhbGxlZCBhIHVuaXQgZnJhY3Rpb24uIEEgcmVwcmVzZW50YXRpb24gb2YgYSBwb3NpdGl2ZSByYXRpb25hbCBudW1iZXIgcFwvcSBhcyB0aGUgc3VtIG9mIGZpbml0ZWx5IG1hbnkgdW5pdCBmcmFjdGlvbnMgaXMgY2FsbGVkIGEgcGFydGl0aW9uIG9mIHBcL3EgaW50byB1bml0IGZyYWN0aW9ucy4gRm9yIGV4YW1wbGUsIDFcLzIgKyAxXC82IGlzIGEgcGFydGl0aW9uIG9mIDJcLzMgaW50byB1bml0IGZyYWN0aW9ucy4gVGhlIGRpZmZlcmVuY2UgaW4gdGhlIG9yZGVyIG9mIGFkZGl0aW9uIGlzIGRpc3JlZ2FyZGVkLiBGb3IgZXhhbXBsZSwgd2UgZG8gbm90IGRpc3Rpbmd1aXNoIDFcLzYgKyAxXC8yIGZyb20gMVwvMiArIDFcLzYuPFwvcD5cclxuXHJcbjxwPkZvciBnaXZlbiBmb3VyIHBvc2l0aXZlIGludGVnZXJzIHAsIHEsIGEsIGFuZCBuLCBjb3VudCB0aGUgbnVtYmVyIG9mIHBhcnRpdGlvbnMgb2YgcFwvcSBpbnRvIHVuaXQgZnJhY3Rpb25zIHNhdGlzZnlpbmcgdGhlIGZvbGxvd2luZyB0d28gY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgcGFydGl0aW9uIGlzIHRoZSBzdW0gb2YgYXQgbW9zdCBuIG1hbnkgdW5pdCBmcmFjdGlvbnMuPFwvbGk+XHJcblx0PGxpPlRoZSBwcm9kdWN0IG9mIHRoZSBkZW5vbWluYXRvcnMgb2YgdGhlIHVuaXQgZnJhY3Rpb25zIGluIHRoZSBwYXJ0aXRpb24gaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIGEuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIChwLHEsYSxuKSA9ICgyLDMsMTIwLDMpLCB5b3Ugc2hvdWxkIHJlcG9ydCA0IHNpbmNlPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvQzAwOS5naWZcIiBzdHlsZT1cImhlaWdodDoxNTZweDsgd2lkdGg6MTA0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+ZW51bWVyYXRlcyBhbGwgb2YgdGhlIHZhbGlkIHBhcnRpdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBhdCBtb3N0IDIwMCBkYXRhIHNldHMgZm9sbG93ZWQgYnkgYSB0ZXJtaW5hdG9yLjxcL3A+XHJcblxyXG48cD5BIGRhdGEgc2V0IGlzIGEgbGluZSBjb250YWluaW5nIGZvdXIgcG9zaXRpdmUgaW50ZWdlcnMgcCwgcSwgYSwgYW5kIG4gc2F0aXNmeWluZyBwLHEgJmx0Oz0gODAwLCBhICZsdDs9IDEyMDAwIGFuZCBuICZsdDs9IDcuIFRoZSBpbnRlZ2VycyBhcmUgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuXHJcbjxwPlRoZSB0ZXJtaW5hdG9yIGlzIGNvbXBvc2VkIG9mIGp1c3Qgb25lIGxpbmUgd2hpY2ggY29udGFpbnMgZm91ciB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gSXQgaXMgbm90IGEgcGFydCBvZiB0aGUgaW5wdXQgZGF0YSBidXQgYSBtYXJrIGZvciB0aGUgZW5kIG9mIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBiZSBjb21wb3NlZCBvZiBsaW5lcyBlYWNoIG9mIHdoaWNoIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIuIE5vIG90aGVyIGNoYXJhY3RlcnMgc2hvdWxkIGFwcGVhciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcblxyXG48cD5UaGUgb3V0cHV0IGludGVnZXIgY29ycmVzcG9uZGluZyB0byBhIGRhdGEgc2V0IHAsIHEsIGEsIG4gc2hvdWxkIGJlIHRoZSBudW1iZXIgb2YgYWxsIHBhcnRpdGlvbnMgb2YgcFwvcSBpbnRvIGF0IG1vc3QgbiBtYW55IHVuaXQgZnJhY3Rpb25zIHN1Y2ggdGhhdCB0aGUgcHJvZHVjdCBvZiB0aGUgZGVub21pbmF0b3JzIG9mIHRoZSB1bml0IGZyYWN0aW9ucyBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gYS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d