시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 55 18 10 76.923%

문제

분수 중에서 분자가 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+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjljY1x1YzU3ZCAocCwgcSwgYSwgbilcdWM3NzQgKDIsIDMsIDEyMCwgMylcdWM3N2MgXHViNTRjIFx1YjJmNVx1Yzc0MCA0XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcLzMgPSAxXC8zKzFcLzMgPSAxXC8yKzFcLzYgPSAxXC80KzFcLzQrMVwvNiA9IDFcLzMrMVwvNisxXC82PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggcCwgcSwgYSwgblx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7KHAsIHEgJmx0Oz0gODAwLCBhICZsdDs9IDEyMDAwLCBuICZsdDs9IDcpPFwvcD5cclxuXHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0Jm5ic3A7XHViZDg0XHVkNTYwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlVuaXQgRnJhY3Rpb24gUGFydGl0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BIGZyYWN0aW9uIHdob3NlIG51bWVyYXRvciBpcyAxIGFuZCB3aG9zZSBkZW5vbWluYXRvciBpcyBhIHBvc2l0aXZlIGludGVnZXIgaXMgY2FsbGVkIGEgdW5pdCBmcmFjdGlvbi4gQSByZXByZXNlbnRhdGlvbiBvZiBhIHBvc2l0aXZlIHJhdGlvbmFsIG51bWJlciBwXC9xIGFzIHRoZSBzdW0gb2YgZmluaXRlbHkgbWFueSB1bml0IGZyYWN0aW9ucyBpcyBjYWxsZWQgYSBwYXJ0aXRpb24gb2YgcFwvcSBpbnRvIHVuaXQgZnJhY3Rpb25zLiBGb3IgZXhhbXBsZSwgMVwvMiArIDFcLzYgaXMgYSBwYXJ0aXRpb24gb2YgMlwvMyBpbnRvIHVuaXQgZnJhY3Rpb25zLiBUaGUgZGlmZmVyZW5jZSBpbiB0aGUgb3JkZXIgb2YgYWRkaXRpb24gaXMgZGlzcmVnYXJkZWQuIEZvciBleGFtcGxlLCB3ZSBkbyBub3QgZGlzdGluZ3Vpc2ggMVwvNiArIDFcLzIgZnJvbSAxXC8yICsgMVwvNi48XC9wPlxyXG5cclxuPHA+Rm9yIGdpdmVuIGZvdXIgcG9zaXRpdmUgaW50ZWdlcnMgcCwgcSwgYSwgYW5kIG4sIGNvdW50IHRoZSBudW1iZXIgb2YgcGFydGl0aW9ucyBvZiBwXC9xIGludG8gdW5pdCBmcmFjdGlvbnMgc2F0aXNmeWluZyB0aGUgZm9sbG93aW5nIHR3byBjb25kaXRpb25zLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBwYXJ0aXRpb24gaXMgdGhlIHN1bSBvZiBhdCBtb3N0IG4gbWFueSB1bml0IGZyYWN0aW9ucy48XC9saT5cclxuXHQ8bGk+VGhlIHByb2R1Y3Qgb2YgdGhlIGRlbm9taW5hdG9ycyBvZiB0aGUgdW5pdCBmcmFjdGlvbnMgaW4gdGhlIHBhcnRpdGlvbiBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gYS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgKHAscSxhLG4pID0gKDIsMywxMjAsMyksIHlvdSBzaG91bGQgcmVwb3J0IDQgc2luY2U8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9DMDA5LmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE1NnB4OyB3aWR0aDoxMDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5lbnVtZXJhdGVzIGFsbCBvZiB0aGUgdmFsaWQgcGFydGl0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGF0IG1vc3QgMjAwIGRhdGEgc2V0cyBmb2xsb3dlZCBieSBhIHRlcm1pbmF0b3IuPFwvcD5cclxuXHJcbjxwPkEgZGF0YSBzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgZm91ciBwb3NpdGl2ZSBpbnRlZ2VycyBwLCBxLCBhLCBhbmQgbiBzYXRpc2Z5aW5nIHAscSAmbHQ7PSA4MDAsIGEgJmx0Oz0gMTIwMDAgYW5kIG4gJmx0Oz0gNy4gVGhlIGludGVnZXJzIGFyZSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+VGhlIHRlcm1pbmF0b3IgaXMgY29tcG9zZWQgb2YganVzdCBvbmUgbGluZSB3aGljaCBjb250YWlucyBmb3VyIHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBJdCBpcyBub3QgYSBwYXJ0IG9mIHRoZSBpbnB1dCBkYXRhIGJ1dCBhIG1hcmsgZm9yIHRoZSBlbmQgb2YgdGhlIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGJlIGNvbXBvc2VkIG9mIGxpbmVzIGVhY2ggb2Ygd2hpY2ggY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlci4gTm8gb3RoZXIgY2hhcmFjdGVycyBzaG91bGQgYXBwZWFyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgaW50ZWdlciBjb3JyZXNwb25kaW5nIHRvIGEgZGF0YSBzZXQgcCwgcSwgYSwgbiBzaG91bGQgYmUgdGhlIG51bWJlciBvZiBhbGwgcGFydGl0aW9ucyBvZiBwXC9xIGludG8gYXQgbW9zdCBuIG1hbnkgdW5pdCBmcmFjdGlvbnMgc3VjaCB0aGF0IHRoZSBwcm9kdWN0IG9mIHRoZSBkZW5vbWluYXRvcnMgb2YgdGhlIHVuaXQgZnJhY3Rpb25zIGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byBhLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==