#include <bits/stdc++.h>
#define modulo 1000003

using namespace std;

int a[100005], n, k;

int main()
{
    int i, cnt, p;
    ifstream fin("grigo.in");
    fin >> n >> k;
    for (i = 1; i <= n; ++i)
        fin >> a[i];
    fin.close();

    /// cnt[i] = numarul de posibilitati de a aranja
    /// intr-o permutare valida numerele 1..i
    cnt = 1;
    p = 1;
    for (i = 1; i <= n; ++i)
        if (a[i] == p) p++;
        else
        {
            cnt = (1LL * (i - 1) * cnt) % modulo;
        }

    ofstream fout("grigo.out");
    fout << cnt << "\n";
    fout.close();

    return 0;
}