Steps - Number of Ways

In how many ways can you reach the n-th step if you can take a step to the next, skip one, or skip two steps?

Input

A single integer n - representing the step number (n ≤ 60).

Output

Print the number of ways to reach the n-th step.

Examples