N = int(input())
M = int(input())
MOD = 10**9
N = N//1000
r = N%M
memo = {}
def f(n,k):
    if k>n or k<0:return 0
    if k==n or k==0:return 1
    if (n,k) in memo:return memo[(n,k)]
    memo[(n,k)] = (f(n-1,k-1)+f(n-1,k))%MOD
    return memo[(n,k)]
print(f(M,r))