Skip to content
AlgoArena

The Promotion Challenge

Easy 1 s 256 MBdynamic-programmingmathcombinatorics

Every morning, your boss walks up a flight of nn stairs to reach the office. He challenges you with a proposition:

"Every single day, you must climb these stairs using a unique sequence of steps—taking either 11 step or 22 steps at a time. Once you have exhausted every single possible combination without repeating a pattern, you get promoted."

Given the total number of steps nn, determine how many distinct days it will take for you to finally earn that promotion (i.e., find the total number of distinct ways to climb the stairs).

Input

A single integer n (1≤n≤451 \le n \le 45), representing the total number of steps in the staircase.

Output

Print a single integer — the total number of distinct ways to reach the top.

Notes

  • Two sequences of steps are considered distinct if at least one step differs in order (e.g., 1+21+2 and 2+12+1 are two different sequences).

Log in to rate this problem5.0 average · 1 ratings

Examples

Input 1
3
Output 1
3

Explanation

For a staircase with n=3n = 3 steps, there are 3 distinct ways to reach the top by taking either 11 or 22 steps at a time:

  1. Way 1 (1+1+11 + 1 + 1): Take three single steps (1→1→11 \rightarrow 1 \rightarrow 1).

  2. Way 2 (1+21 + 2): Take one single step, followed by one double leap (1→21 \rightarrow 2).

  3. Way 3 (2+12 + 1): Take one double leap, followed by one single step (2→12 \rightarrow 1).

Total distinct sequences: 33

image

Input 2
6
Output 2
13