You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. Write a program to count the number of ways, the person can reach the top.

Problem Note

  • Given n will be a positive integer.

Example 1

Input: n = 1
Output: 1 
Explanation: There is only one way to climb to the top

Example 2

Input: n = 2
Output: 2 
Explanation: There are two ways to climb to the top: 
(1, 1) and (2)

Example 3

Input: n = 4
Output: 5 
Explanation: There are five ways to climb to the top: 
(1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1) and (2, 2)