#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 100010
#define v 1000003

int n,m,k;
int poz[MAX_N];
long long sol;

int main() {
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    for (int i = 0; i < m; i++) scanf("%d ",&poz[i]);
    sort(poz, poz + m);

    k = 0; sol = 1;
    for (int i = poz[0]; i <= n; i++)
        if (i == poz[k]) k++;
        else sol = (1L * (i - 1) * sol) % v;
        
    printf("%lld\n",sol);    

    return 0;
}