#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1000003;
const int MAXN = 1e6;

int f[MAXN + 1];
int i_f[MAXN + 1];

int qp(int a, int b, int mod) {
    int res = 1;
    while(b>0){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init() {
    f[0]=1;
    for (int i=1; i<=MAXN;++i) {
        f[i]=f[i-1]*i%MOD;
    }
    i_f[MAXN]=qp(f[MAXN],MOD-2,MOD);
    for (int i=MAXN-1;i>=0;--i) {
        i_f[i]=i_f[i+1]*(i+1)%MOD;
    }
}

signed main() {
    freopen("Binaria.in","r",stdin);
    freopen("Binaria.out","w",stdout);
    init();
    int N, K;
    scanf("%lld%lld",&N,&K);
    int M=N-K+1;
    vector<int> s(M);
    for (int i=0;i<M;++i) {
        scanf("%lld",&s[i]);
    }
    vector<int> d;
    if(M>1){
        d.resize(M-1);
        for (int i=0;i<M-1;++i) {
            d[i]=s[i+1]-s[i];
        }
    }
    int L=d.size();
    vector<int> fixed(K, -1);
    bool iok = true;
    for (int j = 0; j < K; ++j) {
        int ps = j;
        int sum_d = 0;
        while (ps < L) {
            sum_d += d[ps];
            if (sum_d == 1) {
                if (fixed[j] == -1) {
                    fixed[j] = 0;
                } else if (fixed[j] == 1) {
                    iok = false;
                    break;
                }
            } else if (sum_d == -1) {
                if (fixed[j] == -1) {
                    fixed[j] = 1;
                } else if (fixed[j] == 0) {
                    iok = false;
                    break;
                }
            }
            ps += K;
        }
        if (!iok) break;
    }
    if (!iok) {
        printf("0\n");
        return 0;
    }
    int s_fixed = 0;
    int f_cnt = 0;
    for (int val : fixed) {
        if (val == -1) {
            f_cnt++;
        } else {
            s_fixed += val;
        }
    }
    int r = s[0] - s_fixed;
    if (r < 0 || r > f_cnt) {
        printf("0\n");
    } else {
        int ans = f[f_cnt] * i_f[r] % MOD;
        ans = ans * i_f[f_cnt - r] % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}