program grigo;
var  t:array[1..100006]of boolean;
     s,n,m,i:longint;f,g:text;
begin
    assign(f,'grigo.in');reset(f);
    assign(g,'grigo.out');rewrite(g);
     readln(f,n,m);
     for i:=1 to m do begin
      read(f,s);t[s]:=true;
      end;
      s:=1;
      for i:=1 to n do
       if t[i]=false then s:=(s*(i-1))mod 1000003;
       write(g,s);
       close(f);close(g);
       end.