memo = {1: 1, 2: 2, 3: 4}

def r(n):
    # Write your code here
    if n <= 0:
        return 0
    if n in memo:
        return memo[n]
    result = r(n-1) + r(n-2) + r(n-3)
    memo[n] = result
    return result
    
def stepPerms(n):
    return r(n) % (10**10 + 7)