시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 73 22 14 58.333%

문제

분수 중에서 분자가 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이 입력된다. (p, q <= 800, a <= 12000, n <= 7)

출력

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

예제 입력 1

2 3 120 3

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI0MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM3MDQgXHViZDg0XHVjMjE4XHViODVjIFx1YmQ4NFx1ZDU2MCIsImRlc2NyaXB0aW9uIjoiPHA+XHViZDg0XHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWJkODRcdWM3OTBcdWFjMDAgMVx1Yzc3NFx1YWNlMCBcdWJkODRcdWJhYThcdWFjMDAgXHVjNTkxXHVjMjE4XHVjNzc4IFx1YWM4M1x1Yzc0NCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJkODRcdWMyMTggcFwvcVx1Yjk3YyBcdWM3MjBcdWQ1NWNcdWFjMWNcdWM3NTggXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWM1YzhcdWM3NDQgXHViNTRjIHBcL3FcdWI5N2MgXHViMmU4XHVjNzA0XHViZDg0XHVjMjE4XHViODVjIFx1YmQ4NFx1ZDU2MFx1ZDU4OFx1YjJlNFx1YWNlMCBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMlwvM1x1YjI5NCAxXC8yKzFcLzZcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJkODRcdWQ1NjBcdWM1ZDBcdWMxMWMgXHViMzU0XHVkNTU4XHVhZTMwXHVjNzU4IFx1YzIxY1x1YzExY1x1YjljYyBcdWJjMTRcdWIwMTAgXHVhYzgzXHVjNzQwIFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMVwvNisxXC8yXHVjNjQwIDFcLzIrMVwvNlx1Yzc0MCBcdWFjMTlcdWM3NDAgXHViZDg0XHVkNTYwXHViODVjIFx1YmNmOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NThcdWM4MTVcdWMyMTggcCwgcSwgYSwgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YjJlNFx1Yzc0YyBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBwXC9xXHVjNzU4IFx1YmQ4NFx1ZDU2MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPm5cdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YjJlOFx1YzcwNFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZDg0XHVkNTYwXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWIyZThcdWM3MDRcdWJkODRcdWMyMThcdWM3NTggXHViZDg0XHViYWE4XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjZjFcdWM3NDAgYVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjljY1x1YzU3ZCAocCwgcSwgYSwgbilcdWM3NzQgKDIsIDMsIDEyMCwgMylcdWM3N2MgXHViNTRjIFx1YjJmNVx1Yzc0MCA0XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcLzMgPSAxXC8zKzFcLzMgPSAxXC8yKzFcLzYgPSAxXC80KzFcLzQrMVwvNiA9IDFcLzMrMVwvNisxXC82PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggcCwgcSwgYSwgblx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7KHAsIHEgJmx0Oz0gODAwLCBhICZsdDs9IDEyMDAwLCBuICZsdDs9IDcpPFwvcD5cclxuXHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0Jm5ic3A7XHViZDg0XHVkNTYwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNDA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVW5pdCBGcmFjdGlvbiBQYXJ0aXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkEgZnJhY3Rpb24gd2hvc2UgbnVtZXJhdG9yIGlzIDEgYW5kIHdob3NlIGRlbm9taW5hdG9yIGlzIGEgcG9zaXRpdmUgaW50ZWdlciBpcyBjYWxsZWQgYSB1bml0IGZyYWN0aW9uLiBBIHJlcHJlc2VudGF0aW9uIG9mIGEgcG9zaXRpdmUgcmF0aW9uYWwgbnVtYmVyIHBcL3EgYXMgdGhlIHN1bSBvZiBmaW5pdGVseSBtYW55IHVuaXQgZnJhY3Rpb25zIGlzIGNhbGxlZCBhIHBhcnRpdGlvbiBvZiBwXC9xIGludG8gdW5pdCBmcmFjdGlvbnMuIEZvciBleGFtcGxlLCAxXC8yICsgMVwvNiBpcyBhIHBhcnRpdGlvbiBvZiAyXC8zIGludG8gdW5pdCBmcmFjdGlvbnMuIFRoZSBkaWZmZXJlbmNlIGluIHRoZSBvcmRlciBvZiBhZGRpdGlvbiBpcyBkaXNyZWdhcmRlZC4gRm9yIGV4YW1wbGUsIHdlIGRvIG5vdCBkaXN0aW5ndWlzaCAxXC82ICsgMVwvMiBmcm9tIDFcLzIgKyAxXC82LjxcL3A+XHJcblxyXG48cD5Gb3IgZ2l2ZW4gZm91ciBwb3NpdGl2ZSBpbnRlZ2VycyBwLCBxLCBhLCBhbmQgbiwgY291bnQgdGhlIG51bWJlciBvZiBwYXJ0aXRpb25zIG9mIHBcL3EgaW50byB1bml0IGZyYWN0aW9ucyBzYXRpc2Z5aW5nIHRoZSBmb2xsb3dpbmcgdHdvIGNvbmRpdGlvbnMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIHBhcnRpdGlvbiBpcyB0aGUgc3VtIG9mIGF0IG1vc3QgbiBtYW55IHVuaXQgZnJhY3Rpb25zLjxcL2xpPlxyXG5cdDxsaT5UaGUgcHJvZHVjdCBvZiB0aGUgZGVub21pbmF0b3JzIG9mIHRoZSB1bml0IGZyYWN0aW9ucyBpbiB0aGUgcGFydGl0aW9uIGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byBhLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiAocCxxLGEsbikgPSAoMiwzLDEyMCwzKSwgeW91IHNob3VsZCByZXBvcnQgNCBzaW5jZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL0MwMDkuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjEwNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPmVudW1lcmF0ZXMgYWxsIG9mIHRoZSB2YWxpZCBwYXJ0aXRpb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgYXQgbW9zdCAyMDAgZGF0YSBzZXRzIGZvbGxvd2VkIGJ5IGEgdGVybWluYXRvci48XC9wPlxyXG5cclxuPHA+QSBkYXRhIHNldCBpcyBhIGxpbmUgY29udGFpbmluZyBmb3VyIHBvc2l0aXZlIGludGVnZXJzIHAsIHEsIGEsIGFuZCBuIHNhdGlzZnlpbmcgcCxxICZsdDs9IDgwMCwgYSAmbHQ7PSAxMjAwMCBhbmQgbiAmbHQ7PSA3LiBUaGUgaW50ZWdlcnMgYXJlIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5UaGUgdGVybWluYXRvciBpcyBjb21wb3NlZCBvZiBqdXN0IG9uZSBsaW5lIHdoaWNoIGNvbnRhaW5zIGZvdXIgemVyb3Mgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIEl0IGlzIG5vdCBhIHBhcnQgb2YgdGhlIGlucHV0IGRhdGEgYnV0IGEgbWFyayBmb3IgdGhlIGVuZCBvZiB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgYmUgY29tcG9zZWQgb2YgbGluZXMgZWFjaCBvZiB3aGljaCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyLiBObyBvdGhlciBjaGFyYWN0ZXJzIHNob3VsZCBhcHBlYXIgaW4gdGhlIG91dHB1dC48XC9wPlxyXG5cclxuPHA+VGhlIG91dHB1dCBpbnRlZ2VyIGNvcnJlc3BvbmRpbmcgdG8gYSBkYXRhIHNldCBwLCBxLCBhLCBuIHNob3VsZCBiZSB0aGUgbnVtYmVyIG9mIGFsbCBwYXJ0aXRpb25zIG9mIHBcL3EgaW50byBhdCBtb3N0IG4gbWFueSB1bml0IGZyYWN0aW9ucyBzdWNoIHRoYXQgdGhlIHByb2R1Y3Qgb2YgdGhlIGRlbm9taW5hdG9ycyBvZiB0aGUgdW5pdCBmcmFjdGlvbnMgaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIGEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=