N,M,r=int(input())//1000,int(input()),1
for i in range(1,N%M+1):r=r*(M-i+1)//i
print(r%10**9)