Một xâu nhị phân là xâu chỉ gồm các ký tự 0 và 1. Cho số nguyên dương n, hãy đếm số xâu nhị phân độ
dài n không chứa hai ký tự 1 đứng cạnh nhau.
Vì kết quả có thể rất lớn, hãy in phần dư của kết quả khi chia cho 1 000 000 007.
2. Dữ liệu vào
Một dòng duy nhất chứa số nguyên n.
3. Dữ liệu ra
In ra một số nguyên là số xâu nhị phân thỏa mãn yêu cầu, lấy modulo 1 000 000 007.

bài cơ bản của quy hoạch động, cần mn giải thích công thức

NHẮC LẠI: không cần code, chỉ cần giải thích công thức