from functools import lru_cache


@lru_cache
def count(last, left):
    if left == 0:
        return 1
    c = 0
    for d in range(10):
        if sum(last) + d <= 9:
            c += count((last[-1], d), left - 1)
    return c


def euler_164():
    c = 0
    for d in range(1, 10):
        c += count((d, ), 20-1)
    return c


if __name__ == "__main__":
    solution = euler_164()
    print("e164.py: " + str(solution))
    assert solution == 378158756814587