1073 - Xâu tam phân

Tạo bởi: CLB Olympic Tin học HUTECH

Mô tả yêu cầu

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ữ liệu vào

Dòng đầu là một số nguyên n (1 \leq n \leq 10^5)

Dữ liệu ra

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

Ví dụ

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

Gợi ý/Hướng dẫn

Trong ví dụ thứ nhất có 8 xâu: 00, 01, 02, 10, 12, 20, 21, 22

Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB