n=int(input())
m=int(input())
r=int(n/1000)%m
ans=1
div=1
for i in range(1,r+1):
    ans*=m-r+i
    div*=i
print(int(ans/div)%1000000000)