{DINH QUANG DAT TIN 07-10}
{GRIGO}
CONST
 TFI='grigo.in';
 TFO='grigo.out';
 MAX=21;
 e=1000003;
TYPE
 arr1int=array[0..MAX] of longint;
VAR
 fi,fo:text;
 m,n:longint;
 res:int64;
 free:array[0..MAX] of boolean;
 f:array[0..MAX,0..1 shl 20] of longint;

PROCEDURE       input;
var
 i,x:longint;
begin
 assign(fi,tfi);reset(fi);
  read(fi,n,m);
  fillchar(free,sizeof(free),false);
  for i:= 1 to m do
   begin
    read(fi,x);
    free[x]:=true;
   end;
 close(fi);
end;

PROCEDURE       init;
begin
 res:=0;
 fillchar(f,sizeof(f),255);
end;

PROCEDURE       go(i,mask:longint;var x:int64);
var
 j,fi:longint;
 cnt:int64;
begin
 if i>n then
  begin
   x:=(x+1) mod e;
   exit;
  end;
 if f[i][mask]<>-1 then
  begin
   x:=(x+f[i][mask]) mod e;
   exit;
  end;
 cnt:=0;
 if free[i] then
  begin
   for j:= n downto 1 do
    if mask and (1 shl (j-1))=0 then go(i+1,mask or (1 shl (j-1)),cnt)
     else break;
  end
  else
   begin
    fi:=n+1;
    for j:= n downto 1 do
     if mask and (1 shl (j-1))>0 then
      begin
       fi:=j;
       break;
      end;
    for j:=1 to fi-1 do
     if mask and (1 shl (j-1))=0 then
      go(i+1,mask or (1 shl (j-1)),cnt);
   end;
 x:=(x+cnt) mod e;
 f[i][mask]:=cnt;
end;

PROCEDURE       process;
begin
 go(1,0,res);
end;

PROCEDURE       output;
begin
 assign(fo,tfo);rewrite(fo);
  writeln(fo,res);
 close(fo);
end;

BEGIN
 input;
 init;
 process;
 output;
END.