MOD = 10**9

def factor_out_2_5(n):
    a = 0
    while n % 2 == 0 and n != 0:
        a += 1
        n //= 2
    b = 0
    while n % 5 == 0 and n != 0:
        b += 1
        n //= 5
    return a, b, n

def compute_combination(n, k, mod):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1 % mod

    sum2 = 0
    sum5 = 0
    res = 1

    for i in range(1, k + 1):
        numerator = n - i + 1
        denominator = i

        a_n, b_n, num_rest = factor_out_2_5(numerator)
        a_d, b_d, den_rest = factor_out_2_5(denominator)

        sum2 += a_n - a_d
        sum5 += b_n - b_d

        res = (res * num_rest) % mod
        inv_den_rest = pow(den_rest, -1, mod)
        res = (res * inv_den_rest) % mod

    if sum2 >= 9 or sum5 >= 9:
        return 0

    part2 = pow(2, sum2, mod)
    part5 = pow(5, sum5, mod)
    res = (res * part2) % mod
    res = (res * part5) % mod

    return res

# Read input
N = int(input())
M = int(input())

total = N // 1000
r = total % M

if r == 0:
    print(1)
else:
    print(compute_combination(M, r, MOD))