描述

一个分子为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分解为单位分数的分区数，满足以下两个条件。 该分区是最多n个单位分数之和。分区中单位分数的分母的乘积小于或等于a。 例如，如果$(p,q,a,n) = (2,3,120,3)$，你应该输出4，如下

列出了所有有效的分解为单位分数和的方式。

输入

输入是最多包含200个数据集的序列，后面跟一个终止符。一个数据集是一行包含四个正整数$p、q、a$和$n$，满足$p，q <= 800，a <= 12000$且$n <= 7$。这些整数之间用空格分隔。终止符是由一行组成，包含四个零用空格分隔。它不是输入数据的一部分，而是输入结束的标志。

输出

输出应由多行组成，每行包含一个整数。输出中不应出现其他字符。 对于每个输入数据集 $(p,q,a,n)$，对应的输出整数表示所有满足以下条件的 $p/q$的单位分数分解的数量,要求分解中单位分数的个数不超过 n，解中所有单位分数分母的乘积不超过a。

样例输入

2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0

样例输出

4
7
6
2
42
1
0
9
3

来源

日本2024年国内赛