/*

Problem 10: Count Ways to Reach the Nth Step

Write a recursive function int countWays(int n) to count the number of ways to reach the nth step if you can take 1, 2, or 3
steps at a time. For example, countWays(4) should return 7.

*/

#include <iostream>

void countHelper(int n, int &totalWays, int currentStep){
    if(currentStep == n){
        totalWays++;
        //return;
    }

    if(currentStep>n){
        return;
    }

    countHelper(n, totalWays, currentStep+1);
    countHelper(n, totalWays, currentStep+2);
    countHelper(n, totalWays, currentStep+3);
}

int countWays(int n){
    int totalWays = 0;
    countHelper(n, totalWays, 0);
    return totalWays;
}

int main() {
    int n = 0;
    std::cin>>n;
    int ways = countWays(n);
    std::cout<<ways<<std::endl;
}
/*

The reason for using countWaysHelper(n, currentStep + 1, totalWays), countWaysHelper(n, currentStep + 2, totalWays),
and countWaysHelper(n, currentStep + 3, totalWays) is not because 1, 2, and 3 are prime numbers, but because
the problem specifically allows taking 1, 2, or 3 steps at a time.

*/