Đếm số xâu nhị phân độ dài n (gồm các ký tự 0 và 1) sao cho không có hai chữ số 1 nào đứng liền kề nhau.
Ví dụ với n=3: các xâu hợp lệ là 000, 001, 010, 100, 101 — tất cả là 5 xâu.
Hãy in kết quả mod(109+7).
Một dòng chứa số nguyên n.
0≤n≤106. Quy ước với n=0 chỉ có xâu rỗng nên đáp số là 1.
Một số nguyên là số xâu hợp lệ mod(109+7).
Ví dụ:
Đầu vào:
3
Đầu ra:
5
Giải thích:
Đang tải editor...