const modulo=2000003;
var n,k,i,j,p:longint;
    v:array[1..5010] of longint;
    rez:int64;

procedure desc(n:longint;s:longint);
var d:longint;
begin
while n mod 2=0 do
        begin
        inc(v[2],s);
        n:=n div 2;
        end;
d:=3;
while n>1 do
        begin
        while (n mod d<>0)and(d*d<=n) do
                inc(d,2);
        if d*d>n then
                begin
                inc(v[n],s);
                break;
                end;
        while n mod d=0 do
                begin
                inc(v[d],s);
                n:=n div d;
                end;
        end;
end;

begin
assign(input,'sandokan.in');reset(input);
assign(output,'sandokan.out');rewrite(output);
readln(n,k);
p:=n mod (k-1);
if p=0 then
        p:=k-1;
//tre sa calculez C(n-1,p-1);
n:=n-1;p:=p-1;
if p=0 then
        begin
        writeln('1');
        close(output);
        exit;
        end;
for i:=n-p+1 to n do
        desc(i,1);
for i:=1 to p do
        desc(i,-1);
rez:=1;
for i:=1 to n do
        for j:=1 to v[i] do
                rez:=(rez*i) mod modulo;
writeln(rez);
close(input);close(output);
end.