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 vào

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

Dữ liệu ra

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

Input 1

2

Output 1

8

Giải thích:

• Có \(8\) xâu tam phân thỏa mãn yêu cầu: \(00, 01, 02, 10, 12, 20, 21, 22\).

Ràng buộc:

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