var
	fi, fo : text;
  p : int64;
  v : array [1..100000] of boolean;
  s : array [0..100000] of int64;
  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] := 1
  else
    s[1] := 0;
  for i := 2 to n do
  	if v[i] then
    	s[i] := s[i-1]
    else
    	begin
      	p := s[i-1]*(i-1); // Rezultatul operatiei este int64.
        s[i] := p mod 1000003;
      end;
  write(fo,s[n]);
  close(fo);
end.