Climbing Stairs

You are given an integer n representing the number of stairs in a staircase. Each time you can either climb 1 or 2 stairs. Your task is to determine the number of distinct ways you can climb to the top of the staircase.

The number of ways to climb the stairs is equivalent to computing the Fibonacci sequence, specifically: \( F(n+1) \), where \( F(0)=0,\ F(1)=1 \). More formally, the recurrence relation is given by:

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

Run your solution by reading an integer from standard input and printing the result to standard output.

inputFormat

The input consists of a single integer n (0 ≤ n ≤ 50) given on the standard input representing the total number of stairs.

outputFormat

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

1

1