Alice đang đi lên một cầu thang có \(n\) bậc. Biết rằng mỗi bước, bạn ấy có thể leo 1 hoặc 2 hoặc 3 bậc thang. Hỏi có bao nhiêu cách khác nhau để Alice leo lên cầu thang đó?

Input Specification

Gồm số nguyên dương \(n\) được ghi trên một dòng duy nhất.

Output Specification

In ra kết quả trên một dòng.

Constraints

\(n \leq 30\)

Input Sample

4

Output Sample

7

Explanation for Sample Output

Alice có thể leo theo các cách khác nhau như sau: 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 1 + 3 = 2 + 1 + 1 = 2 + 2 = 3 + 1