Climbing Stairs

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

The recurrence relation for the problem is given by the formula: \(dp(n) = dp(n-1) + dp(n-2)\), with the base cases \(dp(1) = 1\) and \(dp(2) = 2\).

This problem is a classic example of dynamic programming and can also be related to the Fibonacci sequence.

inputFormat

The input consists of a single integer n (\(1 \le n \le 10^5\)) representing the number of steps in the staircase.

The input is read from standard input (stdin).

outputFormat

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

The output should be printed to standard output (stdout).

1

1