#include <fstream>
#define MODULO 2000003
#define int long long
using namespace std;
    ifstream cin("sandokan.in");
    ofstream cout("sandokan.out");
    int pow(int a,int b) {
        if(b==1)
            return a;
        else if(b==0)
            return 1;
        if(b%2==0) {
            a=pow(a,b/2);
            return a*a%MODULO;
        }
        else
            return a*pow(a,b-1)%MODULO;
    }
    int lejand(int n,int nr) {
        int f0=n,s=0;
        while(f0<=nr) {
            s+=nr/f0;
            f0*=n;
            s%=MODULO;
        }
        return s;
    }
    bool ciur[100001];
signed main()
{
    int n,k;
    for(int n=4;n<=100000;n+=2) {
        ciur[n]=true;
    }
    for(int n=3;n*n<=100000;n+=2) {
        if(!ciur[n])
            for(int n2=n*n;n2<=100000;n2+=n) {
                ciur[n2]=true;
            }
    }
    cin>>n>>k;
    n--;
    k=n%(k-1)+1;
    int s=(1<<(lejand(2,n)-lejand(2,n)-lejand(2,n-k)))%MODULO;
    for(int n2=3;n2<=n;n2+=2)
        if(!ciur[n2]) {
            s*=pow(n2,lejand(n2,n)-lejand(n2,k)-lejand(n2,n-k));
            s%=MODULO;
        }
    cout<<s;
    return 0;
}