#include <fstream>

using namespace std;

const int NMAX = 1e5, MOD = 1e6 + 3;
int n, m, x, viz[NMAX + 2], dp[NMAX + 2];

int main() {
    
    ifstream cin("grigo.in");
    ofstream cout("grigo.out");
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        viz[x] = 1;
    }
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        if(viz[i] == 1)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] * (i - 1)) % MOD;
    }
    cout << dp[n] << "\n";
    return 0;
}