const
  maxn = 16;
var
  kk, ans, n, k, i, j, max : longint;
  s, p, a : array[1..maxn] of longint;
  
function nextperm : boolean;
var 
  i, j, t : longint;
begin
  i := n - 1;
  while (i >= 1) and (p[i] > p[i + 1]) do begin
    i := i - 1;
  end;
  if (i = 0) then begin
    nextperm := false;
    exit;
  end;
  j := i + 1;
  while (j <= n) and (p[j] > p[i]) do begin
    j := j + 1;
  end;
  t := p[i];
  p[i] := p[j - 1];
  p[j - 1] := t;
  i := i + 1;
  j := n;
  while (i < j) do begin
    t := p[i]; p[i] := p[j]; p[j] := t;
    i := i + 1;
    j := j - 1;
  end;
  nextperm := true;
end;  
  
begin
  assign(input, 'army.in');
  assign(output, 'army.out');
  reset(input);
  rewrite(output);
  read(n, k);
  for i := 1 to k do begin
    read(a[i]);
  end;
  for i := 1 to n do begin
    p[i] := i;
  end;
  ans := 0;
  while true do begin
    j := 1;
    max := 0;
    for i := 1 to n do begin
      if (p[i] = a[j]) then begin
        j := j + 1;
      end;  
      s[i] := 1;  
      for kk := 1 to i - 1 do begin
        if (p[kk] < p[i]) and (s[kk] + 1 > s[i]) then begin
          s[i] := s[kk] + 1;
        end;
      end;  
      if (s[i] > max) then begin
        max := s[i];
      end;
    end;
{    for i := 1 to n do begin
      write(erroutput, p[i], ' ');
    end;
    writeln(erroutput);
    writeln(erroutput, j, ' ', max, ' ', k);  }
    if (j = k + 1) and (max = k) then begin
      ans := ans + 1;
    end;
    if not(nextperm) then break;
  end;
  writeln(ans);
end.
