Staircase Ascent

EASY10 pts

You are ascending a staircase that consists of exactly n steps to reach the summit. On each move, you have the choice to advance by either 1 step or 2 steps at a time.

Determine the total number of distinct sequences of moves that will take you from the ground level to the top of the staircase.

Each unique ordering of 1-step and 2-step moves that results in reaching exactly n steps is considered a separate path, even if the total count of each step type is the same.

Example

Input

n = 2

Output

2

Explanation

There are exactly two distinct ways to reach the 2nd step:

Take a single step twice: 1 + 1 = 2
Take a double step once: 2

Both sequences successfully reach the summit.

Example

Input

n = 3

Output

3

Explanation

There are exactly three distinct ways to ascend 3 steps:

Single step, single step, single step: 1 + 1 + 1 = 3
Single step followed by double step: 1 + 2 = 3
Double step followed by single step: 2 + 1 = 3

Note that paths 2 and 3 are distinct because the order of moves differs.

Example

Input

n = 5

Output

8

Explanation

The 8 distinct paths to reach step 5 are:

1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
1+2+2
2+1+2
2+2+1

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 45
The result is guaranteed to fit within a 32-bit signed integer.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

You are ascending a staircase that consists of exactly n steps to reach the summit. On each move, you have the choice to advance by either 1 step or 2 steps at a time.

Determine the total number of distinct sequences of moves that will take you from the ground level to the top of the staircase.

Each unique ordering of 1-step and 2-step moves that results in reaching exactly n steps is considered a separate path, even if the total count of each step type is the same.

Staircase Ascent

Hints

Staircase Ascent

Hints