using namespace std;
long long n,k,ans,s;
long long a[100010];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	if(k==1){
		cout<<1;
		return 0;
	}
	else{
		a[1]=1;
		a[2]=2;
		for(int i=3;i<=n;i++){
			if(i<=k){
				a[i]=a[i-1]*2%100003;
			}
			else{
				if(i-k<=2){
					a[i]=(a[i-1]*2-1)%100003;
				}
				else{
					a[i]=(a[i-1]*2-a[i-k-1])%100003;
				}
			}
		}
	}
	ans=a[n];
	cout<<ans;
	return 0;
}
//k=2 : 1 2 3 5 8 13 21 34... 
//	a[3]=a[2]*2-a[1]   
//	a[4]=a[3]*2-a[1]
//	a[5]=a[4]*2-a[2]
//	a[6]=a[5]*2-a[3]
//	a[7]=a[6]*2-a[4]
//	a[8]=a[7]*2-a[5]
//测试点四：输入98765 89
//应输出： 86214
//实际输出：-13789