var t:array [1..100000] of byte;
    i,n,m:longint;
    r:int64;
begin
 assign(input,'grigo.in'); reset(input);
 assign(output,'grigo.out'); rewrite(output);
  readln(n,m);
  for i:=1 to m do begin
   read(r); t[r]:=1;
  end;
  r:=1;
  for i:=1 to n do
   if t[i]=0 then r:=r*(i-1) mod 1000003;
  writeln(r);
 close(input); close(output);
end.