分子是1而分母是正整数的分数叫做单位分数。把一个正有理数p/q分成有限多个单位分数的和的表达形式叫做p/q的单位分数分割。例如，1/2+1/6就是2/3的一种单位分数分割。如果只是相加顺序不同，则被看成同一种分割。例如，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，因为

这样列出所有正确的分割。

输入 fraction.in
输入包括四个正整数p,q,a,n。满足p,q<=800,a<=12000,n<=7。数据间由一个空格隔开。

输出 fraction.out
输出一行只有一个整数。不应该有其他字符存在。

样例输入
2 3 12000 7

样例输出
42