#include<iostream>

using namespace std;

#define MOD 2000003

int C[5005][2];

int main()
{
    int N,K;
    
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);
    
    scanf("%d %d",&N,&K);
    
    int raman=N%(K-1);
    
    if(!raman) raman=K-1;
    
    C[0][0]=1;
    
    for(int i=1;i<=N;++i)
    {
         int cur=i%2;
         int prev=!cur;
         
         C[0][cur]=1;
         C[i][cur]=1;
         
         for(int j=1;j<i;++j)
            C[j][cur]=(C[j-1][prev]+C[j][prev])%MOD;   
    }
    
    printf("%d",C[raman-1][N%2]);
    
    return 0;
}