Câu hỏi hôm nay của phú ông là: Cho số nguyên dương ~n~, hãy liệt kê các xâu tam phân khác nhau có đúng ~n~ kí tự sao cho không có hai kí tự ~1~ liền kề nhau. Biết rằng, xâu tam phân là xâu chỉ chứa kí tự ~0~, ~1~, ~2~.

Bờm cho rằng, để liệt kê hết các xâu thỏa mãn yêu cầu như trên thì tốn rất nhiều giấy. Vì vậy, Bờm đã yêu cầu ông ta cung cấp giấy. Phú ông vốn keo kiệt không muốn mua giấy cho Bờm nên đã đổi câu hỏi mới. Câu hỏi như sau: Đếm số lượng xâu tam phân khác nhau có độ dài đúng bằng ~n~ kí tự sao cho không có hai kí tự ~1~ liền kề nhau. Kết quả tính được có thể rất lớn nên chỉ cần đưa ra đáp án là phần dư của phép chia cho ~10^9 + 7~.

Yêu cầu: Hãy giúp Bờm tìm ra đáp án chính xác với câu hỏi mới của phú ông.

Dữ liệu

Chỉ chứa một số nguyên dương ~n~ (~1 \le n \le 10^5~).

Kết quả

Một số nguyên duy nhất là đáp án cần tìm.

Ví dụ

TAMPHAN.INP

2

TAMPHAN.OUT

8

Giải thích: Có 8 xâu tam phân thỏa mãn yêu cầu là 00, 01, 02, 10, 12, 20, 21, 22.

Giới hạn

• 50% số test tương ứng với 50% số điểm có ~n \le 15~.
• 50% số test còn lại tương ứng với 50% số điểm không có ràng buộc gì thêm.