var f1,f2:text;
    i,n,k,ck:longint;
    x:array[0..5010] of longint;
    a1,a2:array[-2..5010] of longint;

procedure comb(n,k:longint);
var i,j:longint;
begin
        for j:=0 to n do
                a2[j]:=1;
        for i:=1 to k do
                for j:=0 to n do
                begin
                        a1[j]:=a2[j];
                        a2[j]:=(a1[j-1]+a2[j-1]) mod 2000003;
                end;
end;

begin
        assign(f1,'sandokan.in');
        reset(f1);
        assign(f2,'sandokan.out');
        rewrite(f2);
        read(f1,n,k);
        for i:=1 to n do
                read(f1,x[i]);
        ck:=n;
        while ck>=k do
                ck:=ck-k+1;
        comb(n-1,ck-1);
        writeln(f2,a2[n-1]);
        close(f1);
        close(f2);
end.