Đề 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