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

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

print(int(ans % 1000000000))