MOD = 1000000000
n = int(input()) // 1000
m = int(input())
n = n % m

x = 1
for i in range(0, n):
    x *= m - i
    x //= i + 1
    
print(x % MOD)