#include <bits/stdc++.h>

using namespace std;

ifstream fin("grigo.in") ;
ofstream fout("grigo.out") ;

bool t[100005] ;

int main()
{
    int n , k , x , sol = 1 ;
    fin >> n >> k ;
    for ( int i = 1 ; i <= k ; i++ )
        fin >> x , t[x] = true ;
    for ( int i = 1 ; i <= n ; i++ )
        if ( t[i] == 0 )
            sol = ( sol * (i-1) ) %  1000003 ;
    fout << sol ;
}