Nhận thấy những câu hỏi liên quan tới dãy nhị phân là quá dễ so với Bờm, phú ông bèn tìm những câu hỏi khác để thách đố Bờm.

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 \leq n \leq 10^{5})\).

Kết quả:

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

Ví dụ:

Ràng buộc:

+ 50% số test tương ứng với 50% số điểm có \(n \leq 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.