import math
n = int(input())
m = int(input())

#配れる千円札の枚数
n = (n - n % 1000) // 1000
#余る千円札の枚数
surplus = n % m
comb = math.factorial(m) // math.factorial(surplus) // math.factorial(m - surplus)

print(comb % 10**9)