while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
long long dp[100001],a[100001];
void f()
{
a[0]=1;
int i;
for(i=1; i<100001; ++i)//构造2次幂表
a[i]=a[i-1]*2%N;
}
}
int main()
{
f();
int i,n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
dp[m]=1;
for(i=m+1; i<=n; ++i)
{
dp[i]=((dp[i-1]*2%N+a[i-m-1])%N-dp[i-m-1]+N)%N;//状态递推过程
}
cout<
return 0 ;
}