var f1,f2:text;
    i,j,k,n,m,rez,x:longint;
    s,sel,v:array[0..100] of longint;

procedure perm(k:longint);
var i,j,ok:longint;
begin
        if k>n then
        begin
                for i:=1 to n do
                begin
                        ok:=1;
                        for j:=1 to i do
                                if s[i]<s[j] then
                                        ok:=0;
                        if ok<>v[i] then
                                exit;
                end;
                rez:=(rez+1) mod 1000003;
                exit;
        end;
        for i:=1 to n do
                if sel[i]=0 then
                begin
                        sel[i]:=1;
                        s[k]:=i;
                        perm(k+1);
                        sel[i]:=0;
                end;
end;

begin
        assign(f1,'grigo.in');
        reset(f1);
        assign(f2,'grigo.out');
        rewrite(f2);
        read(f1,n,m);
        for i:=1 to m do
        begin
                read(f1,x);
                v[x]:=1;
        end;
        perm(1);
        writeln(f2,rez);
        close(f1);
        close(f2);
end.