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