Cầu thang có n bậc. Mỗi bước, Bit có thể bước lên 1 bậc hoặc 2 bậc. Hỏi có bao nhiêu cách để leo từ mặt đất lên bậc thứ n? Vì kết quả rất lớn, hãy in phần dư khi chia cho 10^9 + 7.
Minh họa số cách leo từng bậc
Dữ liệu vào
Một số nguyên n.
Kết quả
Số cách leo, chia lấy dư cho 10^9 + 7.
Giới hạn
1 ≤ n ≤ 10^6.
Ví dụ 1 – vào
4
Ví dụ 1 – ra
5
Ví dụ 2 – vào
2
Ví dụ 2 – ra
2