def foo(n):
    if n == 0:
        return 17
    elif n == 1:
        return 42
    elif n == 2:
        return 23
    elif n%2 == 0:
        sum = foo(n-1) + foo(n-3)
        return sum + foo(n//2)
    else:
        return foo(n-1) + foo(n-2)

def memoizedFoo(m):
    table = [None]*(m+1)
    def foo(n):
        if table[n] == None:
            if n == 0:
                table[n] = 17
            elif n == 1:
                table[n] = 42
            elif n == 2:
                table[n] = 23
            elif n%2 == 0:
                sum = foo(n-1) + foo(n-3)
                table[n] = sum + foo(n//2)
            else:
                table[n] = foo(n-1) + foo(n-2)
        return table[n]
    return foo(m)

def dpFoo(m):
    table = [None]*(m+1)
    for n in range(m+1):
        if n == 0:
            table[n] = 17
        elif n == 1:
            table[n] = 42
        elif n == 2:
            table[n] = 23
        elif n%2 == 0:
            sum = table[n-1] + table[n-3]
            table[n] = sum + table[n//2]
        else:
            table[n] = table[n-1] + table[n-2]
    return table[m]

def memoizedFoo2(m): # From the 2009-09-30 class, but see the next version.
    table = {}
    def foo(n):
        if not (n in table):
            if n == 0:
                table[n] = 17
            elif n == 1:
                table[n] = 42
            elif n == 2:
                table[n] = 23
            elif n%2 == 0:
                sum = foo(n-1) + foo(n-3)
                table[n] = sum + foo(n//2)
            else:
                table[n] = foo(n-1) + foo(n-2)
        return table[n]
    return foo(m)

def memoizedFoo3(m): # This is a more idiomatic version, using "not in".
    table = {}
    def foo(n):
        if n not in table:
            if n == 0:
                table[n] = 17
            elif n == 1:
                table[n] = 42
            elif n == 2:
                table[n] = 23
            elif n%2 == 0:
                sum = foo(n-1) + foo(n-3)
                table[n] = sum + foo(n//2)
            else:
                table[n] = foo(n-1) + foo(n-2)
        return table[n]
    return foo(m)