<Problem>
http://ntucoder.net/Problem/Details/74
Uses Crt;
Var n,k,i:longint; f:array[0..10000] of int64;
Begin
readln(n,k);
for i:=1 to k+1 do f[i]:=i+1;
for i:=k+2 to n do f[i]:=(f[i-1]+f[i-k-1]) mod 1000000;
writeln(f[n]);
readln;
End.