A fraction whose numerator is \textbf{1 }and whose denominator is a positive integer is called a unit fraction. A representation of a positive rational number \textbf{p/q} as the sum of finitely many unit fractions is called a partition of \textbf{p/q }into unit fractions. For example, \textbf{1/2 + 1/6 }is a partition of \textbf{2/3 }into unit fractions. The difference in the order of addition is disregarded. For example, we do not distinguish \textbf{1/6 + 1/2} from \textbf{1/2 + 1/6}. For given four positive integers \textbf{p}, \textbf{q}, \textbf{a} and \textbf{n}, count the number of partitions of \textbf{p/q} into unit fractions satisfying the following two conditions. \begin{itemize} \item The partition is the sum of at most \textbf{n} many unit fractions. \item The product of the denominators of the unit fractions in the partition is less than or equal to \textbf{a}. \end{itemize} For example, if \textbf{(p,q,a,n) = (2,3,120,3)}, you should report \textbf{4} since \includegraphics{https://static.e-olymp.com/content/2e/2e1fbb3638824ffb3ae12476bdfab84648f7a3cc.jpg} enumerates all of the valid partitions. \InputFile The input is a sequence of at most \textbf{200} data sets followed by a terminator. A data set is a line containing four positive integers \textbf{p}, \textbf{q}, \textbf{a} and \textbf{n }satisfying \textbf{p}, \textbf{q }≤ \textbf{800}, \textbf{a }≤ \textbf{12000} and \textbf{n }≤ \textbf{7}. The integers are separated by a space. The terminator is composed of just one line which contains four zeros separated by a space. It is not a part of the input data but a mark for the end of the input. \OutputFile The output should be composed of lines each of which contains a single integer. No other characters should appear in the output. The output integer corresponding to a data set \textbf{p}, \textbf{q}, \textbf{a}, \textbf{n }should be the number of all partitions of \textbf{p/q }into at most \textbf{n }many unit fractions such that the product of the denominators of the unit fractions is less than or equal to \textbf{a}.