#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("grigo.in");
ofstream cout("grigo.out");

const int MAXN = 100000;
const int MOD = 1000003;

bool visible[1 + MAXN];

int main() {
    int n, m, answer = 1;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        visible[x] = true;
    }
    for (int i = 1; i <= n; i++)
        if (!visible[i])
            answer = ((long long) answer * (i - 1)) % MOD;
    cout << answer << "\n";
    return 0;
}