#include <fstream>


using namespace std ;

const int NMAX = 5003 ;
const int MOD = 2000003 ;
const int INF = 0x3f3f3f3f ;

ifstream fin("sandokan.in") ;
ofstream fout("sandokan.out") ;

long long N, K, A[NMAX], D[NMAX][NMAX] ;

int main()
{


    fin >> N >> K ;

    for(int i = 1 ; i <= N ; ++ i)
        fin >> A[i] ;

    -- N ;
    long long sol = 1 ;
    long long a = 1 ;

    int nr = N %(K - 1) ;

    for(int i = nr + 1 ; i <= N ; ++ i)
        sol = (sol * i) % MOD ;

     nr = N - nr ;

     for(int i = 2 ; i <= nr ; ++ i)
        a = (a * i) % MOD ;

     long long aux = a ;

     for(int i = 1 ; i <= MOD - 3 ; ++ i)
        a = (a * aux) % MOD ;

     sol = (sol * a) % MOD ;

     fout << sol ;

    fin.close() ;
    fout.close() ;
    return  0 ;
}