def convolução(f,g,n):
    return sum([f(i)*g(n-1-i) for i in range(n)])

def Escada(n):
    if n == 0:
        return 1
    return convolução(Escada,Escada,n)
    # # versão "por extenso":
    # soma = 0
    # for i in range(n):
    #     soma += Escada(i)*Escada(n-1-i)
    # return soma

def enumera_caminhos(n):
    if n == 0:
        return {""}
    resposta = set()
    for i in range(n):
        # i representa o ponto onde
        # encostamos na diagonal pela
        # primeira vez após o início
        antes = enumera_caminhos(i)
        depois = enumera_caminhos(n-1-i)
        for caminho_antes in antes:
            for caminho_depois in depois:
                resposta.add("→" + caminho_antes + "↑" + caminho_depois)
    return resposta