Marisa cần phải trèo \(n\) bậc thang mới có thể đến được đền Hakurei trên ngọn núi. Nếu cô bước \(1\), \(2\) hoặc \(3\) bước mỗi lần, có bao nhiêu cách để cô có thể đến ngôi đền?

Input

• Dòng đầu tiên gồm số nguyên \(n\).

Output

• In ra một số nguyên, modulo \(10^9+7\) do đáp án có thể rất lớn.

Điều kiện

• \(1 \le n \le 10^{5}\)

Sample Input 1

4

Sample Output 1

7