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

#define int long long

const int NM = 1e6, MOD = 1e6 + 3;

int N, K, a[NM + 5], d[NM + 5];
int mx[NM + 5], mn[NM + 5];
int cnt = 0, ans = 1;

int binpow(int x, int k)
{
    int res = 1;
    while (k > 0)
    {
        if (k & 1)
            res = res * x % MOD;
        k >>= 1;
        x = x * x % MOD;
    }
    return res;
}

int nCk(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    int res = 1;
    for (int i = n - k + 1; i <= n; i++)
        res = res * i % MOD;
    for (int i = 1; i <= k; i++)
        res = res * binpow(i, MOD - 2) % MOD;
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    for (int i = K; i <= N; i++)
        cin >> a[i];
    for (int i = K + 1; i <= N; i++)
    {
        d[i] = a[i] - a[i - 1];
        mx[i % K] = max(mx[i % K], d[i]);
        mn[i % K] = min(mn[i % K], d[i]);
    }
    for (int i = 0; i < K; i++)
    {
        if (mx[i] - mn[i] > 1)
        {
            cout << 0;
            return 0;
        }
    }
    for (int i = 0; i < K; i++)
        if (mn[i] == -1)
        {
            a[K]--;
        }
        else if (mn[i] == mx[i])
            cnt++;
    // for (int i = 1; i <= N; i++)
    // {
    //     cout << a[i] << ' ';
    // }
    // cout << endl;
    // for (int i = 1; i <= N; i++)
    // {
    //     cout << d[i] << ' ';
    // }
    // cout << endl;
    // for (int i = 1; i <= N; i++)
    // {
    //     cout << mx[i] << ' ';
    // }
    // cout << endl;
    // for (int i = 1; i <= N; i++)
    // {
    //     cout << mn[i] << ' ';
    // }
    // cout << endl;
    // cout << cnt;
    cout << nCk(cnt, a[K]);
    return 0;
}