Ways to climb a staircase

Problem

A staircase has n steps. A person climbs one or two steps at a time. Print the number of different ways to reach the top.

Example 1

Input

Output

The ways are 1111, 112, 121, 211 and 22.

Example 2

Input

Output

Try the problem first. Open one hint at a time.

Hint 1

The last move was one step from n - 1 or two steps from n - 2.

Hint 2

Keep only the last two counts in two variables.

Write your Python code, run it on the examples and submit it to hidden tests.