using System;

using System.Collections.Generic;

using System.Numerics;

public class Program

{

    public static void Main()

    {

        var calculator = new StairClimbingPossibilitiesCalculator();

        Console.WriteLine(calculator.Climb(190));

    }

}

​

public class StairClimbingPossibilitiesCalculator

{

    private int[] stepVariations = new int[] {1, 2, 3};

    private Dictionary<int, BigInteger> cachedPossibilitesByStepsCount = new Dictionary<int, BigInteger>();

    public BigInteger Climb(int stepsCount)

    {

        if (stepsCount < 0)

        {

            return 0;

        }

        if (stepsCount == 0)

        {

            return 1;

        }

        BigInteger cachedPossibilitiesCount = 0;

        if (cachedPossibilitesByStepsCount.TryGetValue(stepsCount, out cachedPossibilitiesCount))

        {

            return cachedPossibilitiesCount;

        }

        BigInteger possibilites = 0;

        foreach(int stepVariation in stepVariations)

        {

            possibilites += Climb(stepsCount - stepVariation);

        }

        cachedPossibilitesByStepsCount.Add(stepsCount, possibilites);

        return possibilites;

    }

}