/*#include <cstdio>

#define MOD 2000003

using namespace std;

long long n , k , ramas , i , x , inv , ins;
long long R;

void gcd(long long &x, long long &y, long long a, long long b)
{
     if (!b)
         x = 1, y = 0;
     else
     {
         gcd(x, y, b, a % b);
         long long aux = x;
         x = y;
         y = aux - y * (a / b);
     }
}


int main()
{
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);

    /// combinari de (n - 1) luate cate (n % k - 1)

    scanf("%lld %lld", &n, &k);

    ramas = n % (k-1); ramas--; n--;

    /// combinari de (n) luate cate (ramas)
    /// n! / ramas! * (n - ramas)!

    R = 1;

    for (i = 1; i <= n; ++i)
        R = R * i % MOD;

    for (i = 1; i <= ramas; ++i)
    {
        inv = 0;
        gcd(inv , ins , i , MOD);
        if (inv <= 0) inv = MOD + inv % MOD;
        R = R * inv % MOD;
    }

    for (i = 1; i <= n - ramas; ++i)
    {
        inv = 0;
        gcd(inv , ins , i , MOD);
        if (inv <= 0) inv = MOD + inv % MOD;
        R = R * inv % MOD;
    }

    printf("%lld\n", R % MOD);

    return 0;
}
*/

#include <cstdio>

#define MOD 2000003

using namespace std;

int n , k , ramas , R , i , x;

int A[20000];

void inmultire(int x)
{
    int T = 0;
    for (int i = 1; i <= A[0]; ++i)
    {
        A[i] = A[i] * x + T;
        T = A[i] / 10;
        A[i] = A[i] % 10;
    }

    while (T)
    {
        A[++A[0]] = T % 10;
        T /= 10;
    }
}

void impartire(int x)
{
    R = 0;
    for (int i = A[0]; i; --i)
    {
        R = R * 10 + A[i];
        A[i] = R / x;
        R %= x;
    }

    while (!A[A[0]] && A[0] > 1) A[0]--;
}

int main()
{
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);

    /// combinari de (n - 1) luate cate (n % k - 1)

    scanf("%d %d", &n, &k);

    for (i = 1; i <= n; ++i)
     scanf("%d", &x);

    ramas = n % (k-1); ramas--; n--;

    /// combinari de (n) luate cate (ramas)
    /// n! / ramas! * (n - ramas)!

    A[0] = A[1] = 1;

    if (n - ramas < ramas)
    {
        /// (ramas + 1) * (ramas + 2) * ... * (n) / (n - ramas)!
        for (i = ramas + 1; i <= n; ++i)
            inmultire(i);

        for (i = 1; i <= n - ramas; ++i)
            impartire(i);
    }
    else
    {
        /// (n - ramas + 1) * (n - ramas + 2) * ... * n / ramas!
        for (i = n - ramas + 1; i <= n; ++i)
            inmultire(i);

        for (i = 1; i <= ramas; ++i)
            impartire(i);
    }

    impartire(MOD);

    printf("%d\n", R);

    return 0;
}