Link đề gốc : http://vnoi.info/problems/show/BINARY2/.
Đề bài :
Đề bài tương tựSPBINARY, nhưng giới hạn lớn hơn
Cho 2 số n và k ( 2<=k <= n <= 10^6)
Hãy đếm xem có bao nhiêu xâu nhị phân độ dài n mà không có quá k số 0 hoặc k số 1 nào liên tiếp nhau.
Input
Gồm 1 dòng duy nhất là 2 số n và k.
Output
Gồm 1 dòng duy nhất là số dãy nhị phân thoả mãn (module 10^9).
Example
Input:
3 2
Output:
6