Three kinds of steps

Problem

A hall has n stairs. A visitor climbs one, two or three stairs at a time. Print the number of different ways to reach the top.

Example 1

Input

Output

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

Example 2

Input

Output

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

Hint 1

Add the ways for n - 1, n - 2 and n - 3.

Hint 2

The ways to stand on the ground, step 0, is 1.

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