var
	fi, fo : text;
  p, s : int64;
  v : array [1..100000] of boolean;
  i, j, m, n : integer;
begin
	assign(fi,'grigo.in');  reset(fi);
  assign(fo,'grigo.out'); rewrite(fo);
  readln(fi, n, m);
  for i := 1 to m do
  	begin
  		read(fi, j);
      v[j] := true; // Pozitia p este vizibila.
    end;
  if v[1] then
    s := 1
  else
    s := 0;
  for i := 2 to n do
  	if not v[i] then
    	begin
      	p := s*(i-1); // Rezultatul operatiei este int64.
        s := p mod 1000003;
      end;
  write(fo,s);
  close(fo);
end.