Cho 2 số \(n\) và \(k\) ( \(2\le k \le n \le 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

3 2 

6