import sys

MOD = 10**9

def comb(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0:
        return 1
    # Minimize the loop count by using k and n-k properties
    k = min(k, n - k)
    result = 1
    for i in range(1, k+1):
        result = result * (n - i + 1) // i
        result %= MOD  # Keep the result manageable by modding at each step
    return result

def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    
    total_1000 = N // 1000
    X = total_1000 // M
    K = total_1000 - X * M
    
    print(comb(M, K) % MOD)

if __name__ == "__main__":
    main()