Triple Step Climbing

You are given a staircase with n steps, and you are allowed to take 1, 2, or 3 steps at a time. Your task is to determine the number of unique ways to climb the staircase.

The solution is based on the recurrence relation in which the number of ways to reach step \(i\) is given by

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

for \( i \ge 3 \), with the base conditions \( dp[0] = 1 \), \( dp[1] = 1 \), and \( dp[2] = 2 \).

Implement a program that reads an integer n from standard input and outputs the number of ways to climb n steps to standard output.

inputFormat

The input consists of a single integer n (where \( n \ge 0 \)), read from standard input.

outputFormat

Output a single integer: the number of unique ways to climb n steps, printed to standard output.

## sample

0

1

</p>