Climbing Stairs

Given a staircase with M steps, determine the number of distinct ways you can climb to the top if you can take either 1 or 2 steps at a time. The relationship can be described by the recurrence \(f(M) = f(M-1) + f(M-2)\) with base conditions \(f(0)=1\) and \(f(1)=1\). For example, when \(M=3\), there are 3 distinct ways to climb the stairs: (1,1,1), (1,2), and (2,1).

inputFormat

The input consists of a single integer \(M\) (where \(0 \le M \le 50\)), which represents the total number of steps in the staircase.

outputFormat

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

1

1