```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
const int b=100003;
int n,k,a[1000000],ans=0;
cin>>n>>k;
a[0]=a[1]=1;
for(int i=2;i<=n;++i){
if(i<=k)
a[i]=(a[i-1]*2)%b;
else
a[i]=(a[i-1]*2-a[i-k-1])%b;
}
ans=(a[n]+b)%b;
cout<<ans;
return 0;
}
``````
by safdsfdeaf @ 2024-04-06 11:00:16