{FP}
{$M 64000000,0}
{$MODE OBJFPC}
{$IFDEF ANHDQ}
  {$INLINE OFF}
  {$H-,I+,Q+,R+,S+}
{$ELSE}
  {$INLINE ON}
  {$H+,I-,Q-,R-,S-}
{$ENDIF}

// Result:
program grigo_AnhDQ;

const
  FI_NAME = 'grigo.in';
  FO_NAME = 'grigo.out';
  MaxN    = 100000;
  Radix   = 1000003;

var
  Fi, Fo: Text;
  n     : LongInt;
  A     : array[1..MaxN] of Boolean;
  F     : array[0..MaxN] of LongInt;
(*------------------------------*)
  procedure ReadIn();
  var m, x: LongInt;
  begin
    Assign(Fi, FI_NAME);
    Reset(Fi);
    read(Fi, n, m);
    while m > 0 do
    begin
      Dec(m); read(Fi, x);
      A[x] := true;
    end;
    Close(Fi);
  end;
(*------------------------------*)
  procedure Optimize();
  var i: LongInt;
  begin
    F[0] := 1;
    for i := 1 to n do
      if A[i] then F[i] := F[i - 1]
      else F[i] := (Int64(F[i - 1]) * (i - 1)) mod Radix;
  end;
(*------------------------------*)
  procedure WriteOut();
  begin
    Assign(Fo, FO_NAME);
    Rewrite(Fo);
    WriteLn(Fo, F[n]);
    Close(Fo);
  end;
(*------------------------------*)
begin
  ReadIn();
  Optimize();
  WriteOut();
end.