Problem Description

Naughty Xiaoming finds that when descending stairs, he can take steps of 1 step, 2 steps, or 3 steps at a time. Now there are \( N \) steps in total. Can you help Xiaoming calculate how many different ways there are to descend the stairs?

Input Format

Input consists of a single line containing an integer \( N \).

Output Format

Output a single line containing an integer representing the answer.

Sample Input and Output

Sample Input #1

4

Sample Output #1

7

Sample Input #2

10

Sample Output #2

274

Notes

For all test cases, it is guaranteed that \( 1 \leq N \leq 60 \).

见题面 Input 部分

见题面 Output 部分