A child is running up a staircase with **N steps**, and can hop **1** step, **2** steps or **3** steps at a time. Implement a method to **count how many possible ways the child can run up to the stairs**? You need to return number of possible ways **W**.

**Input format:** Line 1: Integer N (No. of steps)

**Output Format:** Line 1: Integer W i.e. Number of possible ways

**Constraint:** (1 <= N <= 30)

**Sample Input 1:** 4

**Sample Output:** 7

**Explanation:**

In this question, to find out the **number of ways to we can climb the stairs**, we can use a recursive method to solve it. We can call the recursive function thrice in our code with parameters of **(N-1)**, **(N-2)** and **(N-3)** steps (the decrease in steps show the number of steps climbed). And add and return them.

It is one of the typical questions for recursive algorithms.

Algorithm:if(steps <0) // No steps to climb

return 0;

if(steps ==0) //Already reached top

return 1;

i.e. the total ways in which we can climb the steps.

Example:C++ program:Output