N=int(input())//1000
M=int(input())
N%=M

ans = 1
for i in range(N):
    ans *= (M-i)
    ans /= (i+1)

print(ans % 1e9)