#include <fstream>
#include <vector>
using namespace std;
ifstream cin("sandokan.in");
ofstream cout("sandokan.out");
long long n , k ;

long long mod = 2000003;
long long v[ 200005 ];

long long fastexp( long long a ,long long b )
{
    long long prd = 1 ;

    while ( b != 0 )
    {
        if ( b % 2 == 1 )
        {
            prd = ( prd * a ) % mod ;
        }

        a = ( a * a ) % mod ;
        b /= 2 ;
    }
    return prd ;

}

long long inv (long long a )
{
    return fastexp ( a , mod - 2 ) ;
}
int main()
{
    cin >> n >> k ;

    for ( int i = 1; i <= n ; i ++ )
        cin >> v[ i ] ;


        long long val = ( n + 1) % k ;

        vector<int> fact ( n + 1) ;
        fact [ 0 ] =1 ;



    for ( int i = 1; i <= n ; i ++ )
    {
        fact[ i ] = ( fact[ i - 1 ] * i ) % mod ;
    }


    cout<< ((fact[ n - 1  ] * inv(fact [ n - val ])) % mod * inv(fact [val - 1 ])) % mod ;
    return 0;
}