MOD = 10**9

n = int(input())
m = int(input())

s = n // 1000
r = s % m

if r == 0:
    print(1 % MOD)
else:
    r = min(r, m - r)
    dp = [0] * (r + 1)
    dp[0] = 1
    for i in range(1, m + 1):
        # Iterate j in reverse to avoid overwriting values we need
        end = min(i, r)
        for j in range(end, 0, -1):
            dp[j] = (dp[j] + dp[j-1]) % MOD
    print(dp[r] % MOD)