var n,m,i:longint;
    v:array[1..100000]of integer;
    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); v[r]:=1;
 end;
 r:=1;
 for i:=1 to n do
  if v[i]=0 then r:=r*(i-1) mod 1000003;
 writeln(r);
close(input);close(output);
end.