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

using namespace std;

#define MAX_N 100010
#define v 1000003

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

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[poz[0]] = 1;
    for (int i = 1; i <= n; i++)
        if (i == poz[k]) { 
           sol[i] = (sol[i] + sol[i-1]) % v;
           k++;
        }
        else sol[i] += ((i - 1) * sol[i - 1]) % v;
        
    printf("%d\n",sol[n]);    

    return 0;
}