#include <fstream>

#define MOD 1000003
#define DIM 100005

using namespace std;

ifstream f ("grigo.in");
ofstream g ("grigo.out");

long long n , m , ans = 1 , x;
bool v[DIM];

int main() {
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        f >> x;
        v[x] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        if (v[i] == 0) {
            ans = (ans * ((long long)i - 1)) % MOD;
        }
    }

    g << ans;
    return 0;
}