program sandokan;
var f,g:text;
    n,k,x,p,i:longint;

function cmmdc(a,b:longint):longint;
var k:longint;
begin
  k:=a mod b;
  while (k<>0)do
    begin
      a:=b;
      b:=k;
      k:=a mod b;
    end;
  cmmdc:=b;
end;

function comb(k,n:longint):longint;
var v:array[0..5100]of longint;
    i,p,cp,m,s:longint;
begin
  for i:=1 to k do v[i]:=n-k+i;
  for p:=2 to k do
    begin
      cp:=p;
      for i:=1 to k do
        begin
          s:=cmmdc(cp,v[i]);
          cp:=cp div s;
          v[i]:=v[i] div s;
          if (cp=1)then break;
        end;
    end;
  m:=1;
  for i:=1 to k do
    m:=m*v[i] mod 2000003;
  comb:=m;
end;



begin
assign(f,'sandokan.in');
assign(g,'sandokan.out');
reset(f);
rewrite(g);
read(f,n,k);
for i:=1 to n do read(f,x);
p:=1;
while (n>k)do
  begin
    p:=p*comb(k-1,n-1) mod 2000003;
    dec(n,k-1);
  end;
write(g,p);
close(f);
close(g);
end.