题目描述

分子为 $1$ ，分母为正整数的分数称为单位分数。

将正有理数 $p/q$ 表示为有限多个单位分数的总和称为将 $p/q$ 划分为单位分数。

例如，$\frac{1}{2}$ $+$ $\frac{1}{6}$ 是将 $\frac{2}{3}$ 划分为单位分数。

添加顺序的差异被忽略。

例如，我们不区分$\frac{1}{6}$ $+$ $\frac{1}{2}$和$\frac{1}{2}$ + $\frac{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$ $\le$ $800$、 $a$ $\le$ $12000$ 和 $n$ $\le$ $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