program grigo;
var f,g:text;
    n,m,i,nr:longint;
    a:array [1..100000] of 0..1;
    sol:array [0..100000] of longint;

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,nr); a[nr]:=1;
 end;
 sol[0]:=1;
 for i:=1 to n do
  if a[i]=1 then
   sol[i]:=sol[i-1]
  else
   sol[i]:=((i-1)*sol[i-1]) mod 1000003;
  write (g,sol[n]);
 close (f); close (g);
end.