#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <set>
#define ll long long
#define _1 first
#define _2 second
#define _mp make_pair
#define _pb push_back
#define MAX_N 1000003

using namespace std;

ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}

const ll P = 1000003;

ll fp(ll x, ll k)
{
    ll ans = 1;
    for( ; k; k >>= 1, x = x * x % P)
        if(k & 1)
            ans = ans * x % P;
    return ans;
}

ll fac[MAX_N], inv[MAX_N];

ll C(int n, int m)
{
    if(n < m || m < 0)
        return 0;
    //printf("%lld %lld %lld\n", fac[n], inv[n - m], inv[m]);
    return fac[n] * inv[n - m] % P * inv[m] % P;
}

int n, k;
int a[MAX_N];
int sta[MAX_N];

void MAIN()
{
    n = read();
    k = read();
    for(int i = 1; i <= n - k + 1; i++)
        a[i] = read();
    for(int i = 1; i <= n; i++)
        sta[i] = i;
    for(int i = k + 1; i <= n; i++)
    {
        if(abs(a[i - k] - a[i - k + 1]) >= 2)
        {
            printf("0\n");
            return;
        }
        if(a[i - k] == a[i - k + 1])
            sta[i] = sta[i - k];
        else if(a[i - k] < a[i - k + 1])
        {
            if(sta[i - k] == -1)
            {
                printf("0\n");
                return;
            }
            if(sta[i - k] > 0)
                for(int j = i - k; j >= 1; j -= k)
                    sta[j] = 0;
            sta[i] = -1;
        }
        else if(a[i - k] > a[i - k + 1])
        {
            if(!sta[i - k])
            {
                printf("0\n");
                return;
            }
            if(sta[i - k] > 0)
                for(int j = i - k; j >= 1; j -= k)
                    sta[j] = -1;
            sta[i] = 0;
        }
    }
    /*for(int i = 1; i <= n; i++)
        printf("%d ", sta[i]);
    printf("\n");*/
    int sum = a[1], cnt = 0;
    for(int i = 1; i <= k; i++)
        if(sta[i] > 0)
            cnt++;
        else if(sta[i] == -1)
            sum--;
    //printf("%d %d\n", cnt, sum);
    printf("%lld\n", C(cnt, sum));
}

void CLEAR()
{
    ;
}

void EXP()
{
    int n = MAX_N - 1;
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % P;
    inv[n] = fp(fac[n], P - 2);
    for(int i = n - 1; i; i--)
        inv[i] = inv[i + 1] * (i + 1) % P;
}

int main()
{
    EXP();
    int T = 1;
    while(T--)
        MAIN(), CLEAR();
    return 0;
}