#include <fstream>

using namespace std;

const int MAX_N = 1e5;
const int MOD = 1000003;
int cnt[MAX_N + 1];

int main() {
    ifstream fin("grigo.in");
    ofstream fout("grigo.out");
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int pos;
        fin >> pos;
        cnt[pos]++;
    }
    int answer = 1;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) {
            answer = answer * (i - 1) % MOD;
        }
    }
    fout << answer;
    return 0;
}