Climbing Stairs

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

This can be defined recursively using the formula:

\(f(n) = f(n-1) + f(n-2)\) with base cases \(f(0)=1\) and \(f(1)=1\).

Read the integer \(n\) from standard input and print the result to standard output.

inputFormat

The input consists of a single integer n (\(0 \leq n \leq 10^5\) for instance), which represents the number of steps in the staircase.

Input is read from standard input.

outputFormat

Output a single integer which is the number of distinct ways to climb the staircase. The result should be printed to standard output.

0

1