int stepPerms(int n)
{
  vector<int> ring{1, 2, 4};
  if (n < 4) {
    return ring[n - 1];
  }
  int p = 2;
  for (int i = 4; i <= n; i++) {
    p = (p + 1) % 3;
    ring[p] = ring[0] + ring[1] + ring[2];
  }

  return ring[p];
}

def stepPerms(n):
    memo = [-1] * (n+1)
    res = countSteps(n, memo) % 10000000007
    return res

def countSteps(n, memo):
    if n == 0:
        return 1 # Stay where you are
    if n == 1:
        return 1 # There is only 1 way to reach on top by takine 1 step
    if n == 2: 
        return 2 # There are 2 ways 1+1 or 2
    if n == 3:
        return 4 # There are 4 ways 1+1+1 or 2+1 or 1+2 or 3
    if memo[n] != -1:
        return memo[n]
    memo[n] = countSteps(n-1, memo) + countSteps(n-2, memo) + countSteps(n-3, memo)
    return memo[n]
    

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)

def stepPerms(n, memo=None):
    if memo is None:
        memo = [None] * (n + 1)
    if n == 0:
        return 1
    if n < 0:
        return 0
    if memo[n] is None:
        memo[n] = stepPerms(n-1, memo) + stepPerms(n-2, memo) + stepPerms(n-3, memo)
    return memo[n]