Stairs 2

Problem Description

A staircase has $n$ steps. You may climb it by going up one step at a time or two steps at a time.

However, you are not allowed to take three consecutive two-step moves. Compute the number of distinct ways to reach the $n$-th step.

Input Format

A single line containing one integer $n$.

Output Format

Output the total number of ways to climb the stairs.

Sample Input

6

Sample Output

12

Constraints

For $100\%$ of the data, $n \le 50$.