Cầu thang

Một cầu thang có \(n\) bậc. Bạn đứng ở chân cầu thang (bậc \(0\)) và muốn lên bậc thứ \(n\). Mỗi bước, bạn có thể lên 1 bậc hoặc 2 bậc.

Hỏi có bao nhiêu cách khác nhau để lên đến bậc \(n\)? Hai cách khác nhau nếu dãy các bước của chúng khác nhau. Vì đáp án có thể rất lớn, hãy in đáp án modulo \(10^9 + 7\).

Input

• Một số nguyên \(n\) (\(1 \le n \le 10^5\)).

Output

• In số cách lên đến bậc \(n\), modulo \(10^9 + 7\).

Scoring

• Có \(30\%\) số test với \(n \le 30\).

Sample Input 1

4

Sample Output 1

5

Sample Input 2

1

Sample Output 2

1

Notes

Với \(n = 4\) có 5 cách: \(1+1+1+1\), \(1+1+2\), \(1+2+1\), \(2+1+1\), \(2+2\).