Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1106.

Problem Description

Mischievous Xiao Ming found that when going down the stairs, each step can move down $1$ stair, $2$ stairs, or $3$ stairs. Now there are a total of $N$ stairs. Can you help Xiao Ming calculate how many different ways there are?

Input Format

Input one line containing an integer $N$.

Output Format

Output one line containing one integer representing the answer.

4

7

10

274

Hint

For all testdata, it is guaranteed that $1 \leq N \leq 60$.

Translated by ChatGPT 5