//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
#define int long long
int mod = 1e6 +  3;
int pw(int a, int b) {
    int res = 1;
    while (b) {
        if (b % 2) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
int inv(int x) {
    return pw(x, mod - 2);
}
int fac(int n) {
    if (n == 0)
        return 1;
    return fac(n-1)*n%mod;
}
int cnk(int n, int k) {
    int r1 = 1, r2 = 1;
    for (int i = n-k+1; i <= n; ++i) {
        r1 = r1 * i % mod;
    }
    for (int i = 1; i <= k; ++i) {
        r2 = r2 * i % mod;
    }
    return r1 * inv(r2) % mod;
}
void filltrg(string &s, int crd, int mv, char c) {
    while (crd >= 0) {
        if (s[crd] == c)
            return;
        if (s[crd] != '?') {
            cout << "0\n";
            exit(0);
        }
        s[crd] = c;
        crd -= mv;
    }
}
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n - k + 1);
    for (auto &i : a)
        cin >> i;
    string s(n, '?');
    for (int i = k; i < n; ++i) {
        if (abs(a[i-k+1] - a[i-k]) >= 2) {
            cout << "0\n";
            return;
        }
        if (a[i - k + 1] - a[i-k] == 1) {
            s[i] = '1';
            filltrg(s, i-k, k, '0');
        }
        if (a[i - k + 1] - a[i-k] == -1) {
            s[i] = '0';
            filltrg(s, i-k, k, '1');
        }
    }
    int trtr = a[0], op = 0;
    for (int i = 0; i < k; ++i) {
        if (s[i] == '1')
            trtr--;
        if (s[i] == '?')
            op++;
    }
    if (trtr >= 0 and trtr <= op)
        cout << cnk(op, trtr) << '\n';
    else
        cout << "0\n";
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
}