MOD = 10 ** 9
N = int(input()) // 1000
M = int(input())
mod = N % M
if mod == 0:
    print(1)
    exit()

def comb(n, m):
    dp = [0, 1, 0]
    for i in range(1, n + 1):
        dp2 = [0]
        for j in range(i + 1):
            dp2.append((dp[j] + dp[j + 1]) % MOD)
        dp2.append(0)
        dp = dp2
    return (dp[m + 1])

print(comb(M, mod))