Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

result = 0

def dfs(num, dem, k, cur_num, p, q, a, n):
    global result
    #print num, dem, k, cur_num
    #time.sleep(0.5)
    if (num * q) == (dem * p):
        result += 1
        #print "result: " + str(result)
        return

    if k == n:
        return

    if (num * q) > (dem * p):
        return

    i = cur_num
    while i * dem <= a:
        dfs((num * i) + dem, dem * i, k + 1, i, p, q, a, n)
        i += 1

    return

def func():
    while True:
        global result
        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        result = 0
        dfs(0, 1, 0, 1, p, q, a, n)
        print result
        
    return None

if __name__ == '__main__':
    func()
    

Fixed submission:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        #if num * i < dem:
        #   i += 1
        #    continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()
    

Fixed submission:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0


    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        # if num * i < dem:
        #     i += 1
        #     continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()
    

Fixed submission:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        # if num * i < dem:
        #     i += 1
        #     continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()
    

Fixed submission:
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()