#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SIGMA = 26;
const int NMAX = 1e5;
const int MOD = 1000003;

#ifndef HOME
  ifstream fin( "grigo.in" );
  ofstream fout( "grigo.out" );
  #define cin fin
  #define cout fout
#endif // HOME

int fact[NMAX+1];
int inv_fact[NMAX+1];

void euclid( int a, int b, int &x, int &y ) {
  if( b == 0 ) {
    x = 1;
    y = 0;
  }
  else {
    int x0, y0;
    x0 = y0 = 0;
    euclid( b, a % b, x0, y0 );
    x = y0;
    y = x0 - ( a / b ) * y0;
  }
}

int invMod( int x ) {
  int a, b;
  a = b = 0;
  euclid( x, MOD, a, b );
  return a;
}

int combi( int n, int k ) {
  return 1LL * fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

int main() {
  ios_base::sync_with_stdio( false );
  cin.tie( NULL );
  cout.tie( NULL );
  int n, m, i, x;
  cin >> n >> m;
  fact[0] = 1;
  for( i = 1; i <= n; i++ )
    fact[i] = 1LL * fact[i-1] * i % MOD;
  inv_fact[n] = invMod( fact[n] );
  for( i = n - 1; i >= 0; i-- )
    inv_fact[i] = 1LL * inv_fact[i+1] * ( i + 1 ) % MOD;
  int maxi = 0;
  for( i = 0; i < m; i++ ) {
    cin >> x;
    maxi = max( maxi, x );
  }
  cout << combi( m + n - maxi - 1, m - 1 ) * fact[( n - 1 - ( m - 1 ) - ( n - maxi ) )] % MOD * fact[n-maxi] % MOD;
  return 0;
}