Climbing Stairs

A staircase has n steps. Each move climbs either 1 or 2 steps. In how many different ways can you climb to the top? Two ways are different when their sequences of moves differ.

The answer grows fast, so return it as a 64-bit integer.

Constraints

  • 1 ≤ n ≤ 70

Example 1

Input
n = 2
Output
2
Why:

1 + 1, or 2.

Example 2

Input
n = 3
Output
3
Why:

1 + 1 + 1, 1 + 2 or 2 + 1.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –