Bậc Thang & Quy Hoạch Động 1 Chiều Cơ Bản
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một cầu thang có N bậc. Mỗi bước bạn có thể bước lên 1 bậc hoặc 2 bậc. Hãy tính số cách khác nhau để bước từ chân cầu thang (bậc 0) lên tới bậc thứ N, kết quả chia lấy dư cho 10^9 + 7.
Dữ liệu vào (Input)
- Một dòng duy nhất chứa số nguyên dương
N(1 ≤ N ≤ 10^6).
Dữ liệu ra (Output)
- In ra số cách bước lên bậc
Ntheo modulo1000000007.
Ví dụ mẫu
Sample Input 1
3
Sample Output 1
3
Sample Input 2
5
Sample Output 2
8
Community Discussion