import math

n = int(input())
m = int(input())
mod = pow(10, 9)

n //= 1000
n %= m

if n == 0:
    print(1)
    exit()
else:
    print((math.factorial(m) // (math.factorial(n) * math.factorial(m-n))) % mod)