var v : array[1..100] of integer;
    i,j,n,ceva,k,x,d,aux,nr : longint;
    f,g : text;
procedure combin(n,k : longint);
var i,j,start_sus,start_jos,fin_jos,fin_sus : longint;
begin
  start_jos:=1; fin_sus:=n;
  if ceva>n-k then
  begin
    start_sus:=k+1;
    fin_jos:=n-k;
  end
  else
  begin
    start_sus:=n-k+1;
    fin_jos:=k;
  end;
{suuuus }
    for i:=start_sus to fin_sus do
    begin
      d:=2;aux:=i;
      while aux mod d=0 do
      begin
        aux:=aux div d;
        inc(v[d]);
      end;
      d:=3;
      while d<=trunc(sqrt(n)) do
      begin
        while aux mod d=0 do
        begin
          aux:=aux div d;
          inc(v[d]);
        end;
        inc(d,2);
      end;
      if aux<>1 then inc(v[aux]);
    end;
{joooos }
    for i:=start_jos to fin_jos do
    begin
      d:=2;aux:=i;
      while aux mod d=0 do
      begin
        aux:=aux div d;
        dec(v[d]);
      end;
      d:=3;
      while d<=trunc(sqrt(n)) do
      begin
        while aux mod d=0 do
        begin
          aux:=aux div d;
          dec(v[d]);
        end;
        inc(d,2);
      end;
      if aux<>1 then dec(v[aux]);
    end;
end;

begin
assign(f,'sandokan.in');reset(f);
assign(g,'sandokan.out');rewrite(g);
read(f,n,k);
for i:=1 to n do read(f,x);
ceva:=n-(n div (k-1))*(k-1);
if ceva=0 then ceva:=k-1;
if ceva=1 then
  begin
    writeln(g,1);
    close(g);halt;
  end
else combin(n-1,ceva-1);
nr:=1;
for i:=1 to 100 do
    if v[i]<>0 then
       for j:=1 to v[i] do
       nr:=(nr*i)mod 2000003;
writeln(g,nr);
close(g);
end.