Một xâu được gọi xâu tam phân nếu xâu đó chỉ tồn tại các kí tự 0, 1, 2. Hãy đếm số lượng xâu tam phân độ dài n mà không có 2 kí tự 1 liền kề nhau.
Dòng đầu là một số nguyên n (1 \leq n \leq 10^5)
In ra một dòng là số lượng xâu thoả mãn. Kết quả có thể lớn, hãy đưa ra kết quả theo phần dư của 10^9+ 7
| Dữ liệu vào Sao chép |
2 |
| Dữ liệu ra Sao chép |
8 |
| Dữ liệu vào Sao chép |
10 |
| Dữ liệu ra Sao chép |
24960 |
Trong ví dụ thứ nhất có 8 xâu: 00, 01, 02, 10, 12, 20, 21, 22