'''
动态规划递推
利用前缀和将时间复杂度压缩到线性
'''

n, k = map(int, input().split())

# 假设所哟牛从0位置开始排列，dp(i)表示最后一个1在i位置的方案数
S = [0] * n     # dp的前缀和
dp = [0] * n
for i in range(n):
    if i <= k:
        dp[i] = 1
    else:
        dp[i] = S[i-k-1] + 1 # 多加1是前面位置都是全0的情况

    dp[i] %= 5000011

    if i == 0:
        S[i] = dp[i]
    else:
        S[i] = S[i-1] + dp[i]

    S[i] %= 5000011

print((S[n-1] + 1) % 5000011)       # 加1是补上全0的情况