Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction
def solve(p, q, a, n):
    def _solve(f, n, m, s):
        if f < 0 or m > a or n < 0:
            return 0
        if f == 0:
            return 1
        return sum((_solve(f-Fraction(1, i), n-1, m*i, i) for i in range(s, a//m+1)), 0)
    return _solve(Fraction(p, q), n, 1, 1)
        
if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

Fixed submission:
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if num == 0:
            return 1
        if d == 0:
            return 0
        if num * a // m < dem:
            return 0
        return sum((_solve(num*i-dem, dem*i, d-1, m*i, i)
                    for i in range(s, min(dem*n//num, a//m)+1)), 0)
    return _solve(p, q, n, 1, 1)

if __name__ == "__main__":
    ans = []
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        ans.append(solve(p, q, a, n))
    print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if p * dem == q * num:
            return 1
        if p * dem < q * num or d == 0 or dem * s ** d > a:
            return 0
        if p * dem * s - num * q * s > d * q * dem:
            return 0
        return sum((_solve(num*i+dem, dem*i, d-1, m*i, i) for i in range(s, a//m+1)), 0)
    return _solve(0, 1, n, 1, 1)
        
if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

Fixed submission:
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if num == 0:
            return 1
        if d == 0:
            return 0
        if num * a // m < dem:
            return 0
        return sum((_solve(num*i-dem, dem*i, d-1, m*i, i)
                    for i in range(s, min(dem*n//num, a//m)+1)), 0)
    return _solve(p, q, n, 1, 1)

if __name__ == "__main__":
    ans = []
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        ans.append(solve(p, q, a, n))
    print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
from fractions import Fraction

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(f, d, m, s):
        if f == 0:
            return 1
        if d == 0:
            return 0
        if f < Fraction(1, a//m):
            return 0
        return sum((_solve(f-Fraction(1, i), d-1, m*i, i)
                    for i in range(s, min(f.denominator*n//f.numerator, a//m)+1)), 0)
    return _solve(Fraction(p, q), n, 1, 1)

if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

Fixed submission:
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if num == 0:
            return 1
        if d == 0:
            return 0
        if num * a // m < dem:
            return 0
        return sum((_solve(num*i-dem, dem*i, d-1, m*i, i)
                    for i in range(s, min(dem*n//num, a//m)+1)), 0)
    return _solve(p, q, n, 1, 1)

if __name__ == "__main__":
    ans = []
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        ans.append(solve(p, q, a, n))
    print(*ans, sep="\n")