type list=array[1..5000] of longint;
var n,k,max,i,j:longint;
comb:array[0..5000,0..5000] of longint;
a:list;
f:text;
{---------------------}
procedure QuickSort(var A: List; Lo, Hi: Integer);

procedure Sort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := a[(l+r) DIV 2];
  repeat
    while a[i] < x do i := i + 1;
    while x < a[j] do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

begin {QuickSort};
  Sort(Lo,Hi);
end;
{---------------------}
begin
assign(f,'sandokan.in');reset(f);
read(f,n,k);
for i:=1 to n do read(f,a[i]);
close(f);
quicksort(a,1,n);
max:=a[n];
for i:=0 to n-1 do comb[i,0]:=1;
comb[1,1]:=1;
comb[1,0]:=1;
for i:=2 to n-1 do
   for j:=1 to n-1 do
       comb[i,j]:=comb[i-1,j]+comb[i-1,j-1] mod 2000003;
assign(f,'sandokan.out');rewrite(f);
write(f,comb[n-1,max-1] mod 2000003);
close(f);
end.