N=int(input())
M=int(input())

N//=1000
x=N%M
x=min(x,M-x)

ANS=1
for i in range(x):
    ANS*=M-i
    ANS//=i+1

    if ANS%(10**9)==0:
        ANS=0
        break

print(ANS%(10**9))