Counting Ways to Climb Stairs

Little Ming discovered that when climbing down a staircase, he can take 1, 2, or 3 steps at a time. Given a staircase with N steps, compute the number of distinct ways to climb down.

The recurrence relation is given by: $$dp[n] = dp[n-1] + dp[n-2] + dp[n-3]$$ with the base case $$dp[0] = 1$$.

inputFormat

The input consists of a single integer N (where N ≥ 0), representing the number of stairs.

outputFormat

Output a single integer representing the number of ways to climb the staircase.

sample

1

1