Anh nông dân Bo có một đàn bò gồm rất nhiều con cái và con đực. Trong một hội chợ, anh muốn sắp một hàng bò gồm $n$ con. Tuy nhiên những con bò đực rất hung hăng nếu đứng gần nhau, anh phải sắp tối thiểu $k$ con bò cái xen giữa hai con bò đực để chúng khỏi húc nhau.

Bạn hãy giúp anh Bo đếm thử xem có bao nhiêu cách để sắp một hàng gồm $n$ con bò mà hai con bò đực bất kỳ không húc nhau (anh Bo có rất nhiều bò nên không sợ thiếu bò cái hoặc bò đực).

Ví dụ với $n=4$ và $k=1$, ta có 8 cách xếp như sau (M: bò đực, F: bò cái): FFFF, MFFF, FMFF, FFMF, FFFM, MFMF, MFFM, FMFM.

Dữ liệu vào

• Gồm hai số nguyên $n$ và $k$ cách nhau một khoảng trắng $(1\le n,k\le {10}^4)$

Dữ liệu ra

• Số cách xếp hàng thỏa mãn yêu cầu. Do số lượng này có thể rất lớn nên chỉ cần in ra tối đa $6$ chữ số cuối cùng (modulo 10^6).

Input 1

4 1

Output 1

8

Input 2

5 2

Output 2

9