using System;

public class Program

{

    public static void Main()

    {

        // Test Case #1

        //int n = 3;

        int[] queries = {1,3,7};

        foreach(int i in queries)

        {

            Console.WriteLine(stepPerms(i));  // 1 // 4 // 44

        }

        // Test Case #2

        //int   n2 = 2;

        int[] queries2 = {5,8};

        foreach(int i in queries2)

        {

            Console.WriteLine(stepPerms(i)); // 13 // 81

        }

        // Test Case #3

        //int n3 = 3;

        int[] queries3 = {15,20,27};

        foreach(int i in queries3)

        {

            Console.WriteLine(stepPerms(i)); // 5768 // 121415 // 8646064

        }

    }

    // Complete the stepPerms function below.

    static int stepPerms(int n) {

​

        int[] array = new int[n];

        if (n == 1) 

        {

            return 1;

        }

        else if(n == 2) 

        {

            return 2;

        }

        else if(n == 3)

        {

            return 4;

        }

        array[0] = 1;

        array[1] = 2;

        array[2] = 4;

        for (int i = 3; i < n; i++) 

        {

            array[i] = array[i-1] + array[i-2] + array[i-3];

        }

        return array[array.Length-1];

    }

}