import math
N = int(input()) // 1000
M = int(input())
L = N % M
patterns = math.factorial(M) // math.factorial(L) // math.factorial(M-L)
print(patterns % 10**9)