Xếp bò thành hàng

Bác nông dân Bo muốn xếp thành một hàng \(n\) con bò, mỗi con là bò đực (M) hoặc bò cái (F), để đem đi trưng bày. Bò đực rất hung hăng, nên giữa hai con bò đực bất kỳ phải có ít nhất \(k\) con bò cái. Bác có vô hạn cả bò đực lẫn bò cái.

Hãy đếm số cách xếp hàng \(n\) con thoả mãn điều kiện trên (hai cách khác nhau nếu có vị trí mà loại bò khác nhau). Vì số cách có thể rất lớn, chỉ in ra phần dư khi chia cho \(1\,000\,000\).

Ví dụ với \(n = 4\), \(k = 1\) có \(8\) cách: FFFF, MFFF, FMFF, FFMF, FFFM, MFMF, MFFM, FMFM.

Input

Một dòng gồm hai số nguyên \(n\) và \(k\).

Output

In ra số cách xếp theo modulo \(1\,000\,000\) (in số nguyên bình thường, không thêm số \(0\) ở đầu).

Constraints

• \(1 \le n, k \le 10000\)

Sample Input 1

7 2

Sample Output 1

19

Sample Input 2

10 3

Sample Output 2

36

Explanation

Với \(n = 7\), \(k = 2\): xếp không có bò đực có \(1\) cách; có đúng một bò đực có \(7\) cách; hai bò đực có \(10\) cách; ba bò đực chỉ có \(1\) cách (MFFMFFM). Tổng cộng \(1 + 7 + 10 + 1 = 19\).