#include <bits/stdc++.h>
using namespace std; 
const int P = 1e6 + 3; 
const int N = 1e6 + 5; 

inline int poww(int a, int b) {
    int r = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P; 
    return r; 
}

int n, k; 
int s[N], fa[N]; 
int a[N]; 

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int C(int n, int m) {
    if (n < m || m < 0) return 0; 
    int ans = 1;
    for (int i = 1; i <= m; ++i) ans = 1ll * ans * (n - i + 1) % P * poww(i, P - 2) % P;  
    return ans; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> k; 
    for (int i = k; i <= n; ++i) cin >> s[i]; 
    for (int i = 1; i <= n; ++i) fa[i] = i, a[i] = -1; 
    for (int i = k + 1; i <= n; ++i) {
        int y = find(i), x = find(i - k); 
        if (s[i] == s[i - 1]) {
            if (x == y) continue; 
            if (a[x] != -1) fa[y] = x; 
            else fa[x] = y; 
        } else if (s[i] == s[i - 1] - 1) {
            if (x == y) return cout << "0\n", 0; 
            if (a[x] == 0 || a[y] == 1) return cout << "0\n", 0; 
            a[x] = 1, a[y] = 0; 
        } else if (s[i] + 1 == s[i - 1]) {
            if (x == y) return cout << "0\n", 0; 
            if (a[x] == 1 || a[y] == 0) return cout << "0\n", 0; 
            a[x] = 0, a[y] = 1; 
        } else return cout << "0\n", 0; 
    }
    int t = 0, all = k; 
    for (int i = 1; i <= k; ++i) t += (a[i] == 1), all -= (a[i] != -1); 
    t = s[k] - t; 
    // cout << all << ' ' << t << '\n'; 
    cout << C(all, t) << '\n'; 
    return 0; 
}