我们的目的是将一个分数拆分成若干个分子是1分母是正整数的分数之和的形式。例如2/3可以拆分成1/2+1/6的形式。这里不考虑顺序，比如1/6+1/2和1/2+1/6相同。

输入p, q, a, n, 其中p/q为分数，对这个分数进行拆分，要求拆分的分数个数不能多于n个，所有分母的乘积不能大于a。求有多少种拆分方法?

输入：最多200组数据。在每行中都有四个数分别表示p, q, a, n，之间以空格隔开，并且满足p,q<=800，a<=12000，n<=7，最后以四个0做为输入的结束。



输入示例:

2 3 120 3

2 3 300 3

0 0 0 0



输出示例:

4

7-Our aim is to split a fraction into a number of elements is a denominator is a positive integer fraction of the sum of form. For example, 2/3 can be split into 1/2+1/6 form. Not considered here, the order, such as 1/6+1/2 and 1/2+1/6 of the same. Input p, q, a, n, where p/q as a fraction of this split scores require no more than the number of split points n-all the product of the denominator can not be larger than a. How many kinds of demand split method? Input: Up to 200 sets of data. In each line has four numbers indicate the p, q, a, n, separated by a space between, and meet the p, q < = 800, a < = 12000, n < = 7, the end, four 0 as the input end. Input Example: 2,312,032,330,030,000 sample output: 47