#include <cstdio>

const long long maxn = 100002;
const long long mod = 1000003;
long long n, m;
long long a[maxn], dp[maxn];

int main()
{
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);

    scanf("%d %d", &n, &m); 
    //fprintf(stderr,"%d %d\n", n, m);
    int i;
    for (i = 1; i <= m; ++i)
    {
	int j;
	scanf("%d", &j);
	a[j] = 1;
    }

    dp[1] = 1;
    for (i = 2; i <= n; ++i)
	if (a[i]) dp[i] = dp[i-1];
	else dp[i] = ((long long)(i-1) * dp[i-1]) % mod;

    printf("%d", dp[n]); 

    return 0;

}