Staircase Climbing Ways

Diana wants to climb a staircase with n steps. At each move, she can take 1, 2, or 3 steps. Your task is to compute the total number of distinct ways she can reach the top.

The recurrence relation is given by: $$W(n)=W(n-1)+W(n-2)+W(n-3)$$ with the base cases: $$W(1)=1,\; W(2)=2,\; W(3)=4$$. Note that when n is 0, the answer is defined to be 0.

inputFormat

The input consists of a single integer n (where n ≥ 0) representing the number of steps in the staircase. The input is read from standard input (stdin).

outputFormat

Output a single integer on standard output (stdout), which is the number of distinct ways to climb the staircase given that Diana can take 1, 2, or 3 steps at a time.## sample

1

1