Ezvor

10. Climbing Stairs

EasyDynamic Programming Verified judge

You are climbing a staircase that takes n steps to reach the top. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1

Input

2

Output

2

Explanation: 1+1 or 2.

Example 2

Input

3

Output

3

Input format

Input: one integer n.
Output: the number of distinct ways.

Constraints

  • 1 ≤ n ≤ 45

Expected output

2