Hè năm nay, bé An được mẹ mua cho một bộ thẻ số để chơi xếp hình cùng các bạn trong xóm. Từ vòng đầu tiên, An xếp lên bàn đúng \(1\) thẻ. Sang vòng thứ hai, An lại xếp lên bàn đúng \(1\) thẻ vì theo luật chơi không được thay đổi. Đến vòng thứ ba trở đi, An tuân theo một quy tắc bí mật mà bà ngoại dạy: số thẻ của vòng này bằng tổng số thẻ của hai vòng liền trước cộng lại. Cứ thế, vòng nào cũng tuân theo đúng quy tắc ấy, không có ngoại lệ.

Các bạn trong xóm rất thích thú và cứ đếm thử số thẻ của An qua từng vòng. Đến một hôm, các bạn muốn biết ngay ở vòng thứ \(N\) thì An có bao nhiêu thẻ mà không cần đếm tay, vì số \(N\) có thể rất lớn.

Hãy giúp các bạn đó tính số thẻ mà An có ở vòng thứ \(N\).

Đị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ố thẻ của An ở vòng thứ \(N\), lấy phần dư khi chia cho \(10^9 + 7\).

Ví dụ

Input:

6

Output:

8

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.