const x=1000003;
var nrs : array[0..100010] of longint;
    viz : array[0..100010] of byte;
    i,j,n,m : longint;
    v : int64;
    f,g : text;
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,j);
      viz[j]:=1;
    end;
  nrs[1]:=1;
    for i:=2 to n do
      if viz[i]=1 then
        nrs[i]:=nrs[i-1]
      else
      begin
        v:=(nrs[i-1]*(i-1))mod x;
        nrs[i]:=v;
      end;
  writeln(g,nrs[n]);
  close(g);
end.