def binomial_recursive(n, k):
    if k==0 or k==n:
        return (1,((n,k),))

    x = binomial_recursive(n-1, k)
    y = binomial_recursive(n-1, k-1)
    return x[0]+y[0], ((n, k), x[1], y[1])

answer = {}

def binomial_dp(n, k):
    if (n, k) not in answer:
        if k==0 or k==n:
            return (1,((n,k),))

        x = binomial_dp(n-1, k)
        y = binomial_dp(n-1, k-1)
        answer[(n, k)] = x[0] + y[0]
        return answer[ (n, k) ], ((n, k), x[1], y[1])
    else:
        return answer[(n,k)], ((n,k),)

def print_tree(tree, prefix=''):
    label, *children = tree
    print(prefix + "--" + str(label))
    for c in children[:-1]:
        print_tree(c, prefix=prefix + '  |')
    if children:
        print_tree(children[-1], prefix=prefix + '   ')

result = binomial_recursive(7, 5)
print(result[0])  
print_tree(result[1])

#result = binomial_dp(7, 5)
#print(result[0])  
#print_tree(result[1])
