var ap:Array[0..100000] of boolean;
    f,g:text;
    nr,i,n,m,max:longint;
    rez:int64;
    ok:boolean;
begin
 assign(f,'grigo.in'); reset(f);
 assign(g,'grigo.out'); rewrite(g);
 read(f,n,m);
 for i:=1 to m do begin
  read(f,max);
  ap[max-1]:=true;
 end;
 rez:=1;
 for i:=1 to n-1 do
  if ap[i]=false then
   rez:=(rez*i) mod 1000003;
 writeln(g,rez);
 close(f); close(g);
end.