Chung cư của gia đình bé Tý ở tầng rất cao, mỗi ngày cậu đều phải leo cầu thang bộ lên nhà bà ngoại ở tầng trên. Cầu thang có tất cả \(N\) bậc, đánh số từ \(0\) (mặt đất) đến \(N\) (tầng bà ngoại). Vì bậc khá cao và đôi chân còn ngắn, mỗi bước chân Tý chỉ có thể nhảy lên đúng \(1\) bậc hoặc đúng \(2\) bậc một lúc. Cậu tò mò không biết có bao nhiêu cách khác nhau để đi từ mặt đất lên đến tận bậc cuối cùng, vì nhảy kiểu nào cũng đến nơi nhưng trông rất khác nhau.

Hãy giúp Tý đếm xem có bao nhiêu cách leo. Vì số cách có thể rất lớn, bạn chỉ cần in ra phần dư khi chia cho \(10^9 + 7\).

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên \(N\) (\(1 \le N \le 10^7\)).

Định dạng đầu ra

• In ra số cách leo cầu thang, lấy phần dư khi chia cho \(10^9 + 7\).

Ví dụ

Input:

4

Output:

5

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 20\).
• \(30\%\) số điểm ứng với \(N \le 10^5\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.