BINARY2 Xâu nhị phân

Cho 2 số n và k. 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 (2 ≤ k ≤ n ≤  10⁶)

Output: Gồm 1 dòng duy nhất là số dãy nhị phân thoả mãn. (mod 10⁹).

Input	Output	Giải thích
3 2	6	Đó là các xâu 001 , 010 , 011 , 100 , 101 , 110.