def dfs(n):
    if (n == 1):
        return 1
    if (n == 2):
        return 2
    if (res[(n - 1)] == (- 1)):
        res[(n - 1)] = (dfs((n - 1)) + dfs((n - 2)))
        return res[(n - 1)]
    else:
        return res[(n - 1)]
def dfs(n):
    if (n == 1):
        return 1
    if (n == 2):
        return 2
    if (res[(n - 1)] == (- 1)):
        res[(n - 1)] = (dfs((n - 1)) + dfs((n - 2)))
        return res[(n - 1)]
    else:
        return res[(n - 1)]