#include <cstdio>//知识涉及:同余 递归 记忆化搜索
#define mod 100003
int dp[1000010];
int f(int n,int k){
	dp[1] = dp[0] = 1;
	for(int i = 2;i <= n;i++){
		if(i <= k) dp[i] = (dp[i-1]*2)%mod;//同余
		else dp[i] = (dp[i-1]*2 - dp[i-k-1]) % mod;
	}
	return (dp[n]+mod)%mod;//防止负数 -- 同余 
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	printf("%d",f(n,k));
	return 0;
} 
/*f函数公式的推导:
	dp[x] = dp[x-1]+dp[x-2]+...+dp[x-k]
	dp[x-1] = dp[x-2]+dp[x-3]+...+dp[x-k-1]
	我们发现,变成了公差为2的等差数列
	所以 在x<=k时:dp[x] = (2*dp[x-1])%mod
	若x > k:
		dp[x] = dp[x-1]*2-dp[x-k-1]
			dp[x-k-1] --> 首项
			因为若x<=k时 x-k-1<=0 
*/