Leo núi

Linh đang chuẩn bị cho một chuyến leo núi thử thách.
Để đến được đỉnh núi, cô ấy phải vượt qua một cầu thang gồm \(n\) bậc.

Mỗi lần, Linh có thể bước lên 1, 2, hoặc 3 bậc.
Hãy giúp Linh đếm xem có bao nhiêu cách khác nhau để cô ấy có thể lên được đỉnh núi.

Vì kết quả có thể rất lớn, hãy in ra kết quả lấy theo modulo \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\) --- số bậc thang.

Output

• In ra một số nguyên duy nhất --- số cách Linh có thể lên đến đỉnh núi (modulo \(10^9 + 7\)).

Notes

Với \(n = 4\), có \(7\) cách khác nhau để Linh leo lên đỉnh:
\((1,1,1,1)\), \((1,1,2)\), \((1,2,1)\), \((2,1,1)\), \((2,2)\), \((1,3)\), \((3,1)\).

Scoring

• Subtask 1 (20 điểm): \(n \le 20\)

• Subtask 2 (80 điểm): \(n \le 10^5\)