import math

N = int(input())
M = int(input())
amari = N%(1000*M)//1000
print(math.factorial(M)//(math.factorial(amari)*math.factorial(M-amari))%1000000000)