{uses dos;}

var x,i,j,n,m:longint;
s:int64;
a:array[1..100000] of longint;
b:array[1..100000] of boolean;
f,g:text;

{h,mn,se,ms:word;
t:int64;}

begin

{gettime(h,mn,se,ms);
t:=ms+se*100+mn*6000+h*360000;}

assign(f,'grigo.in');
assign(g,'grigo.out');
reset(f);
rewrite(g);
read(f,n,m);
for i:=1 to m do begin
  read(f,x);
  b[x]:=true;
  end;
  x:=0;
for i:=1 to n do
  if b[i] then begin
    inc(x);
    a[x]:=i;
    end;
s:=1;
x:=n;
if a[1]=1 then begin
  for i:=m downto 1 do begin
    for j:=0 to x-a[i]-1 do
      s:=(s*(x-1-j)) mod 1000003;
    x:=a[i];
    end;
  end
  else
  s:=0;
writeln(g,s);
close(f);
close(g);

{gettime(h,mn,se,ms);
t:=ms+se*100+mn*6000+h*360000-t;
writeln(t);}

end.