#include <bits/stdc++.h>
using namespace std;

int n, m, x;
long long d[100005];
bool f[100005];
const int MOD = 1000003;
int main()
{
    freopen("grigo.in", "r", stdin);
    freopen("grigo.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m ; ++i){
        scanf("%d", &x);
        f[x] = 1;
    }
    d[1] = 1;
    for(int i = 2; i <= n ; ++i)
        if(f[i] == 1) d[i] = d[i - 1];
        else d[i] = (1LL * d[i - 1] * (i - 1)) % MOD;
    printf("%lld", d[n]);
    return 0;
}