Simran is running up a staircase with N steps, and can hop(jump) either 1 step, 2 steps or 3 steps at a time.You have to count, how many possible ways Simran can run up to the stairs.

**Input Format:**

Input contains integer N that is number of steps

**Output Format:**

Output for each integer N the no of possible ways w.

**Constraints**

1 <= N <= 30

SAMPLE INPUT | SAMPLE OUTPUT |
---|---|

4 | 7 |

#include <bits/stdc++.h> using namespace std; int solve(int n) { if (n <= 1) return 1; if (n == 2) return 2; if (n == 3) return 4; return solve(n - 1) + solve(n - 2) + solve(n - 3); } int main() { int n; cin >> n; cout << solve(n) << endl; return 0; }

**References**