MOD=10**9
N = int(input())
M = int(input())
N = (N//1000)%M
def nCk(n,k):
	ret = 1
	for i in range(n,n-k,-1):
		ret *= i
	for i in range(k,1,-1):
		ret //= i
	return ret
print(nCk(M,N)%MOD)