Stairs with 1, 2 or 3 steps

Problem

A learner climbs a staircase of n steps, taking 1, 2 or 3 steps at a time. Count the different ways to reach the top, using a cached recursion.

Example

Input

Output

1111, 112, 121, 211, 22, 13, 31 gives 7 ways.

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

Hint 1

The last move was 1, 2 or 3 steps, so add the ways for n - 1, n - 2 and n - 3.

Hint 2

A negative count has no ways, and exactly 0 left has one way.

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