#include <cstdio>

#define MOD 2000003

using namespace std;

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

void gcd(int &x, int &y, int a, int b)
{
     if (!b)
         x = 1, y = 0;
     else
     {
         gcd(x, y, b, a % b);
         int 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("%d %d", &n, &k);

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

    ramas = n % k; ramas--; n--;

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

    R = 1; if (ramas < 0) ramas = 0;

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

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

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

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

    return 0;
}