Climb Stairs

easy

1. You are given a number n, representing the number of stairs in a staircase.
2. You are on the 0th step and are required to climb to the top.
3. In one move, you are allowed to climb 1, 2 or 3 stairs.
4. You are required to print the number of different paths via which you can climb to the top.

Input Format

A number n

Output Format

A number representing the number of ways to climb the stairs from 0 to top.

Constraints

0 &lt;= n &lt;= 20

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

Fibonacci-dp

Climb Stairs With Variable Jumps