Climbing Stairs with 1, 2, or 3 Steps

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 determine the total number of distinct ways you can reach the top of the staircase.

The problem can be formulated as follows:

Let \(dp[n]\) denote the number of ways to climb \(n\) steps. The recurrence relation is given by:

\( dp[n] = dp[n-1] + dp[n-2] + dp[n-3] \)

with the base conditions:

• \(dp[0] = 1\)
• \(dp[1] = 1\)
• \(dp[2] = 2\)
• \(dp[3] = 4\)

Compute \(dp[n]\) and output the result.

inputFormat

The input consists of a single line containing one integer n (0 ≤ n ≤ 10⁶), representing the number of steps in the staircase.

outputFormat

Output a single integer which is the number of distinct ways to climb the staircase.

## sample

0

1

</p>