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

fstream in ( "grigo.in" , ios::in  );
fstream out( "grigo.out", ios::out );

const int DIM = 1e5 + 5;
const int MOD = 1e6 + 3;

bitset<DIM> oki;

int main( void ) {
    
    int n, m;
    in >> n >> m;
    
    for( int i = 1; i <= m; i ++ ) {
        int x;
        in >> x;
        
        oki[x] = true;
    }
    
    int ans = 1;
    for( int i = 1; i <= n; i ++ )
        if( oki[i] == false )
            ans = ( 1LL * ans * (i - 1) ) % MOD;
    
    out << ans << endl;
    return 0;
}