n=int(input())
m=int(input())

amari = (n%(m*1000)) // 1000
mod=10**9

dp=[[0]*(amari+m+1) for i in range(amari+m+1)]
dp[0][0]=1

for i in range(amari+m):
    for j in range(amari+m):
        if dp[i][j] == 0:
            continue
        dp[i+1][j] += dp[i][j]
        dp[i+1][j+1] += dp[i][j]


print(dp[m][amari]%mod)