You are climbing a staircase that has n steps. Each time you may climb either 1 step or 2 steps. In how many distinct ways can you reach the top (step n)?
Two ways are different if, at some point in the climb, the size of the step taken differs. Return the total count.
Input format
A single line containing one integer n.
Output format
A single line containing one integer: the number of distinct ways to climb to the top.
Constraints
- 0 ≤ n ≤ 90
- The answer fits in a 64-bit signed integer (it does for all n in range).
Example
For n = 3 the ways are 1+1+1, 1+2, and 2+1, so the answer is 3.