Cho 2 số ~n~ và ~k~ ~\left( 2 \le k \le n \le 10^6\right)~

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~).

Sample Input

3 2

Sample Output

6