Climbing the Stairs

Problem Background

Special for beginners, ^_^

Problem Description

A staircase has $n$ steps ($71>n>0$). You may climb $1$, $2$, or $3$ steps in a single move. Write a program to compute how many different ways there are to climb to the top.

Input Format

Each line of the input is one test case, giving the number of steps $n$. The last line is $0$, marking the end of the input.

Output Format

For each input line, output the corresponding number of ways on its own line.

Sample Input 1

1
2
3
4
0

Sample Output 1

1
2
4
7

Constraints

1s, 1024KiB for each test case.