Cached = {}


def f(n):
    if n < 2:
        return 1
    if n not in Cached:
        Cached[n] = f(n - 1) + f(n - 2)
        if n >= 3:
            Cached[n] += f(n - 3)
        if n >= 4:
            Cached[n] += f(n - 4)
    return Cached[n]
