Counting Ways to Climb Stairs

You are given a staircase with n steps. You can climb the staircase by taking either 1, 2, or 3 steps at a time. Your task is to compute the number of distinct ways to reach the top of the staircase.

The solution can be formulated using dynamic programming and is based on the recurrence relation:

$$W(n)=\begin{cases} 1 & n=0,\\ 1 & n=1,\\ 2 & n=2,\\ 4 & n=3,\\ W(n-1)+W(n-2)+W(n-3) & n \ge 4. \end{cases}$$

Read an integer n from standard input and output the number of distinct ways to climb the staircase.

inputFormat

The input consists of a single line containing an integer n (0 ≤ n ≤ 10^5), which represents the number of steps in the staircase.

outputFormat

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

## sample

1

1

</p>